2023/05/17 by Wayne Barrett, Shaun Fallat, Barrett, Wayne +9 · 1 citation
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2305.10562
openalex publication_date 2023/05/17 · openalex created_date 2023/05/21 · openalex updated_date 2026/08/01
For an n × n matrix A, let q(A) be the number of distinct eigenvalues of A. If G is a connected graph on n vertices, let S(G) be the set of all real symmetric n × n matrices A=[aij] such that for i≠ j, aij=0 if and only if \i,j\ is not an edge of G. Let q(G)=\rm min\q(A) : A ∈ S(G)\. Studying q(G) has become a fundamental sub-problem of the inverse eigenvalue problem for graphs, and characterizing the case for which q(G)=2 has been especially difficult. This paper considers the problem of determining the regular graphs G that satisfy q(G)=2. The resolution is straightforward if the degree of regularity is 1, 2, or 3. However, the 4-regular graphs with q(G)=2 are much more difficult to characterize. A connected 4-regular graph has q(G)=2 if and only if either G belongs to a specific infinite class of graphs, or else G is one of fifteen 4-regular graphs whose number of vertices ranges from 5 to 16. This technical result gives rise to several intriguing questions.