New and explicit constructions of unbalanced Ramanujan bipartite graphs

Burnwal, Shantanu Prasad and Sinha, Kaneenika and Vidyasagar, Mathukumalli (2022) New and explicit constructions of unbalanced Ramanujan bipartite graphs. The Ramanujan Journal, 57 (3). pp. 1043-1069. ISSN 1382-4090

Text
Ramanujan_Journal.pdf - Published Version
Available under License Creative Commons Attribution.
Download (442kB)

Abstract

The objectives of this article are threefold. Firstly, we present for the first time explicit constructions of an infinite family of unbalanced Ramanujan bigraphs. Secondly, we revisit some of the known methods for constructing Ramanujan graphs and discuss the computational work required in actually implementing the various construction methods. The third goal of this article is to address the following question: can we construct a bipartite Ramanujan graph with specified degrees, but with the restriction that the edge set of this graph must be distinct from a given set of “prohibited” edges? We provide an affirmative answer in many cases, as long as the set of prohibited edges is not too large. © 2021, The Author(s).

[error in script]

IITH Creators:

IITH Creators	ORCiD
Vidyasagar, Mathukumalli	UNSPECIFIED

Item Type:

Article

Additional Information:

S.P.B. was supported through a Senior Research Fellowship from the Ministry of Human Resource Development, Government of India. K.S. was supported by a MATRICS Grant from the Science and Engineering Research Board (SERB), Department of Science and Technology, Government of India. M.V. was supported by a SERB National Science Chair, Government of India.

Uncontrolled Keywords:

Computational complexity; Explicit construction; Ramanujan graphs

Subjects:

Electrical Engineering
Mathematics

Divisions:

Department of Electrical Engineering
Department of Mathematics

Depositing User:

. LibTrainee 2021

Date Deposited:

18 Jul 2022 11:30

Last Modified:

18 Jul 2022 11:30