Spectral characterization of mixed extensions of small graphs

DOI10.1016/J.DISC.2018.02.005MaRDI QIDQ2317641zbMATH OpenOpenAlexFDO

Authors Willem H. Haemers

Publication date 12 August 2019

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph spectrumspectral characterization

Mathematics Subject Classification ID

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

Abstract: A mixed extension of a graph $G$ is a graph $H$ obtained from $G$ by replacing each vertex of $G$ by a clique or a coclique, where vertices of $H$ coming from different vertices of $G$ are adjacent if and only if the original vertices are adjacent in $G$. If $G$ has no more than three vertices, $H$ has all but at most three adjacency eigenvalues equal to $0$ or $-1$. In this paper we consider the converse problem, and determine the class $calG$ of all graphs with at most three eigenvalues unequal to $0$ and $-1$. Ignoring isolated vertices, we find that $calG$ consists of all mixed extensions of graphs on at most three vertices together with some particular mixed extensions of the paths $P_4$ and $P_5$.

Recommendations

• On the spectral characterization of mixed extensions of P₃
• Mixed graphs with smallest eigenvalue greater than \(- \frac{ \sqrt{ 5} + 1}{ 2} \)
• Mixed graphs with smallest eigenvalue greater than \(- \sqrt{3}\)
• On spectral integral variations of mixed graphs
• Nonsingular mixed graphs with few eigenvalues greater than two

Cites work

• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 3394189 (Why is no real title available?)
• Bipartite graphs with at most six non-zero eigenvalues
• On the nullity of bipartite graphs
• Spectra of graphs
• The graphs with all but two eigenvalues equal to \(-2\) or 0
• The graphs with all but two eigenvalues equal to \(\pm 1\)

Cited in

(12)

• On the spectral characterization of mixed extensions of P₃
• On graphs with exactly one anti-adjacency eigenvalue and beyond
• Mixed graphs with smallest eigenvalue greater than \(- \frac{ \sqrt{ 5} + 1}{ 2} \)
• Self-converse mixed graphs are extremely rare
• Signed graphs with all but two eigenvalues equal to \(\pm 1\)
• Spectral spread and trace norm of eccentricity matrix of graphs
• Spectral determination of graphs with one positive anti-adjacency eigenvalue
• Bipartite graphs with all but two eigenvalues equal to \(0\) and \(\pm 1\)
• On two problems related to anti-adjacency (eccentricity) matrix
• Graphs with large multiplicity of \(-2\) in the spectrum of the eccentricity matrix
• The complete classification of graphs whose second largest eigenvalue of the eccentricity matrix is less than 1
• On claw-free graphs with all but four eigenvalues equal to \(0\) or \(-1\)

This page was built for publication: Spectral characterization of mixed extensions of small graphs

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