On split graphs with four distinct eigenvalues

DOI10.1016/J.DAM.2019.09.016MaRDI QIDQ2306591zbMATH OpenOpenAlexWikidataFDO

Authors Felix Goldberg, Anu Varghese, S. J. Kirkland, A. Vijayakumar

Publication date 23 March 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

adjacency matrixbidegreed graphcombinatorial designsplit graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: It is a well-known fact that a graph of diameter $d$ has at least $d+1$ eigenvalues. Let us call a graph emph{$d$-extremal} if it has diameter $d$ and exactly $d+1$ eigenvalues. Such graphs have been intensively studied by various authors. %Much attention has been devoted to the study of graphs that are extremal with respect to this relation: emph{i.e} have diameter $d$ and exactly $d+1$ distinct eigenvalues. A graph is emph{split} if its vertex set can be partitioned into a clique and a stable set. Such a graph has diameter at most $3$. We obtain a complete classification of the connected bidegreed $3$-extremal split graphs. We also show how to construct certain families of non-bidegreed $3$-extremal split graphs.

Recommendations

• A complete characterization of bidegreed split graphs with four distinct signless Laplacian eigenvalues
• scientific article; zbMATH DE number 1225794
• Characterization of split graphs with at most four distinct eigenvalues
• On the spectrum of an extremal graph with four eigenvalues
• On graphs with distinct eigenvalues

Cites work

• A new family of symmetric 2-(\(v, k, {\lambda{}}\)) block designs
• Characterization of split graphs with at most four distinct eigenvalues
• Class-uniformly resolvable pairwise balanced designs with block size two and three
• Combinatorial Designs
• Eigenspaces of graphs
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 4141876 (Why is no real title available?)
• scientific article; zbMATH DE number 3910422 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 867473 (Why is no real title available?)
• Matrix Analysis
• Nonregular graphs with three eigenvalues
• On characterizing certain graphs with four eigenvalues by their spectra
• On some infinite series of \((r,1)\)-designs
• On the spectrum of an extremal graph with four eigenvalues
• Schur complements and statistics
• Spectra of graphs
• Split graphs
• Split non-threshold Laplacian integral graphs
• Two spectral characterizations of regular, bipartite graphs with five eigenvalues
• Variations on a theorem of Ryser

Cited in

(15)

• A complete characterization of bidegreed split graphs with four distinct signless Laplacian eigenvalues
• 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 regular graphs with four distinct eigenvalues
• A_ and L_-spectral properties of spider graphs
• Energy of graphs with no eigenvalue in the interval \((-1,1)\)
• Complete characterization of the bidegreed split graphs with three or four distinct \(A_{\alpha}\)-eigenvalues
• On split graphs with three or four distinct (normalized) Laplacian eigenvalues
• Digraphs with few distinct eigenvalues
• Parameterized algorithms for editing to uniform cluster graph
• On the complexity of the eigenvalue deletion problem
• Bounds for the distance spectral radius of split graphs
• Modifying graphs to bound the number of distinct eigenvalues
• Parameterized algorithms for editing to uniform cluster graph

Describes a project that uses

Uses Software

• MathOverflow

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

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