On regular graphs with four distinct eigenvalues

DOI10.1016/J.LAA.2016.09.043zbMATH Open1348.05125arXiv1605.05421OpenAlexW2405779299MaRDI QIDQ332649FDOQ332649

Authors: Xueyi Huang, Qiongxiang Huang 

Publication date: 8 November 2016

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

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.

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

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

zbMATH Keywords

eigenvaluesregular graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (32)

• Characterization of split graphs with at most four distinct eigenvalues
• Graphs with at most Four Seidel Eigenvalues
• On the spectrum of an extremal graph with four eigenvalues
• On the graphs with four distinct domination roots
• On graphs with three distinct signless Laplacian eigenvalues
• Two characterizations of the grid graphs
• On split graphs with three or four distinct (normalized) Laplacian eigenvalues
• Graphs with fourth Laplacian eigenvalue less than two
• Two spectral characterizations of regular, bipartite graphs with five eigenvalues
• On the embedding of graphs into graphs with few eigenvalues
• Graphs with many valencies and few eigenvalues
• On 2-equitable graphs
• Characterization of graphs with an eigenvalue of large multiplicity
• The graph with spectrum \(14^{1} 2^{40}( - 4)^{10}( - 6)^{9}\)
• The eigenvalues of the graphs \(D(4,q)\)
• 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\)
• Graphs with few distinct eigenvalues and extremal energy
• Graphs with four distinct Laplacian eigenvalues
• Seidel spectrum of threshold graphs
• On the multiplicity of the least signless Laplacian eigenvalue of a graph
• Characterisation of all integral circulant graphs with multiplicative divisor sets and few eigenvalues
• Characterization of graphs with some normalized Laplacian eigenvalue of multiplicity \(n - 3\)
• More on graphs with just three distinct eigenvalues
• 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
• Monotonic normalized heat diffusion for regular bipartite graphs with four eigenvalues
• On graphs whose smallest distance (signless Laplacian) eigenvalue has large multiplicity
• Regularity and the spectra of graphs
• On the multiplicity of Laplacian eigenvalues for unicyclic graphs
• The characterization of graphs with eigenvalue -1 of multiplicity n-4 or n-5

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)