Equitable partitions for Ramanajun graphs

2021/07/24 by Mohsen Alinejad, Alinejad, Mohsen, Sanaz Fulad +1
Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2107.11563

openalex publication_date 2021/07/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For d-regular graph G, an edge-signing sigma:E(G) → -1,1 is called a good signing if the absolute eigenvalues of adjacency matrix are at most 2 √(d-1). Bilu-Linial conjectured that for each regular graph there exists a good signing. In this paper, by using new concept "Equitable Partition", we solve the Bilu-Linial Conjecture for some cases. We show that how to find out a good signing for special complete graphs and lexicographic product of two graphs. In particular, if there exist two good signings for graph G, then we can find a good signing for a 2-lift of G.

Citations

• Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees

Related

• On the signed graphs with two distinct eigenvalues
• Some regular signed graphs with only two distinct eigenvalues
• The signed graphs with two eigenvalues unequal to ± 1
• Parity families and a kernel-averaged L-function for near-Ramanujan signings
• On signed graphs with at most two eigenvalues unequal to ± 1