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

[img] 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 CreatorsORCiD
Vidyasagar, MathukumalliUNSPECIFIED
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
URI: http://raiith.iith.ac.in/id/eprint/9626
Publisher URL: http://doi.org/10.1007/s11139-021-00384-0
OA policy: https://v2.sherpa.ac.uk/id/publication/17023
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 9626 Statistics for this ePrint Item