On regular graphs with four distinct eigenvalues

DOI10.1016/J.LAA.2016.09.043MaRDI QIDQ332649zbMATH OpenOpenAlexFDO

Authors Xueyi Huang, Qiongxiang Huang

Publication date 8 November 2016

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.05421

zbMATH Keywords

eigenvaluesregular graphs

Mathematics Subject Classification ID

Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: Let $mathcalG(4,2)$ be the set of connected regular graphs with four distinct eigenvalues in which exactly two eigenvalues are simple, $mathcalG(4,2,-1)$ (resp. $mathcalG(4,2,0)$) the set of graphs belonging to $mathcalG(4,2)$ with $-1$ (resp. $0$) as an eigenvalue, and $mathcalG(4,geq-1)$ the set of connected regular graphs with four distinct eigenvalues and second least eigenvalue not less than $-1$. In this paper, we prove the non-existence of connected graphs having four distinct eigenvalues in which at least three eigenvalues are simple, and determine all the graphs in $mathcalG(4,2,-1)$. As a by-product of this work, we characterize all the graphs belonging to $mathcalG(4,geq-1)$ and $mathcalG(4,2,0)$, respectively, and show that all these graphs are determined by their spectra.

Recommendations

• Regular graphs with four eigenvalues
• Graphs with four distinct Laplacian eigenvalues
• Regular graphs of degree at most four that allow two distinct eigenvalues
• Distance-regular graphs with an eigenvalue of multiplicity four
• On split graphs with four distinct eigenvalues
• Small regular graphs with four eigenvalues
• On the spectrum of an extremal graph with four eigenvalues
• Integral circulant graphs with four distinct eigenvalues
• On graphs with three or four distinct normalized Laplacian eigenvalues
• Strongly regular graphs with nonprincipal eigenvalue 4 and its extensions

Cites work

• A nonregular analogue of conference graphs
• Biregular graphs with three eigenvalues
• Combinatorial designs with two singular values. I: Uniform multiplicative designs
• Combinatorial designs with two singular values. II: Partial geometric designs
• Feasibility conditions for the existence of walk-regular graphs
• GRAPHS WITH A SMALL NUMBER OF DISTINCT EIGENVALUES
• Graphs with many valencies and few eigenvalues
• scientific article; zbMATH DE number 3869370 (Why is no real title available?)
• Multiplicative cones - a family of three eigenvalue graphs
• Nonregular graphs with three eigenvalues
• On graphs with exactly one eigenvalue less than -1
• On graphs with just three distinct eigenvalues
• On graphs with three eigenvalues
• Regular graphs with four eigenvalues
• Small regular graphs with four eigenvalues
• The Gewirtz graph: An exercise in the theory of graph spectra
• The graphs with all but two eigenvalues equal to \(\pm 1\)
• The non-bipartite graphs with all but two eigenvalues in \([-1,1]\)
• Which graphs are determined by their spectrum?

Cited in

(36)

• Spectra of regular polytopes
• Graphs with fourth Laplacian eigenvalue less than two
• A spectral characterization of the \(s\)-clique extension of the square grid graphs
• Graphs with at most three distance eigenvalues different from \(-1\) and \(-2\)
• Regular graphs with four eigenvalues
• Two characterizations of the grid graphs
• Graphs with few distinct eigenvalues and extremal energy
• Monotonic normalized heat diffusion for regular bipartite graphs with four eigenvalues
• Seidel spectrum of threshold graphs
• On the multiplicity of the least signless Laplacian eigenvalue of a graph
• Characterization of graphs with some normalized Laplacian eigenvalue of multiplicity \(n - 3\)
• Characterization of graphs with an eigenvalue of large multiplicity
• Characterization of split graphs with at most four distinct eigenvalues
• The eigenvalues of the graphs \(D(4,q)\)
• On the spectrum of an extremal graph with four eigenvalues
• On the graphs with four distinct domination roots
• Regularity and the spectra of graphs
• The graph with spectrum \(14^{1} 2^{40}( - 4)^{10}( - 6)^{9}\)
• On graphs whose smallest distance (signless Laplacian) eigenvalue has large multiplicity
• On the embedding of graphs into graphs with few eigenvalues
• More on graphs with just three distinct eigenvalues
• On graphs with three distinct signless Laplacian eigenvalues
• On the multiplicity of Laplacian eigenvalues for unicyclic graphs
• On 2-equitable graphs
• Graphs with many valencies and few eigenvalues
• Two spectral characterizations of regular, bipartite graphs with five eigenvalues
• The characterization of graphs with eigenvalue -1 of multiplicity n-4 or n-5
• Regular graphs of degree at most four that allow two distinct eigenvalues
• Graphs with two main and two plain eigenvalues
• Complete characterization of the bidegreed split graphs with three or four distinct \(A_{\alpha}\)-eigenvalues
• Graphs with at most Four Seidel Eigenvalues
• Characterisation of all integral circulant graphs with multiplicative divisor sets and few eigenvalues
• On split graphs with three or four distinct (normalized) Laplacian eigenvalues
• Graphs with four distinct Laplacian eigenvalues
• On the least eigenvalue of genuine strongly 3-walk-regular graphs
• On walk-semiregular graphs with three or four distinct eigenvalues

This page was built for publication: On regular graphs with four distinct eigenvalues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q332649)