Spectral characterizations of almost complete graphs

DOI10.1016/J.DAM.2013.08.002MaRDI QIDQ403557zbMATH OpenOpenAlexFDO

Authors Marc Cámara, Willem H. Haemers

Publication date 29 August 2014

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

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

zbMATH Keywords

cospectral graphsgraph spectrumspectral characterization

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We investigate when a complete graph $K_n$ with some edges deleted is determined by its adjacency spectrum. It is shown to be the case if the deleted edges form a matching, a complete graph $K_m$ provided $mleqn-2$, or a complete bipartite graph. If the edges of a path are deleted we prove that the graph is determined by its generalized spectrum (that is, the spectrum together with the spectrum of the complement). When at most five edges are deleted from $K_n$, there is just one pair of nonisomorphic cospectral graphs. We construct nonisomorphic cospectral graphs (with cospectral complements) for all $n$ if six or more edges are deleted from $K_n$, provided $n$ is big enough.

Recommendations

• Per-spectral and adjacency spectral characterizations of a complete graph removing six edges
• Spectral characterizations of two families of nearly complete bipartite graphs
• Spectral characterization of the complete graph removing a path of small length
• Spectral characterization of the complete graph removing a path
• Per-spectral characterizations of some bipartite graphs

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?)
• A note on cospectral graphs
• Constructing cospectral graphs
• Cospectral graphs and the generalized adjacency matrix
• Developments on spectral characterizations of graphs
• On the generalized spectral characterization of graphs having an isolated vertex
• On the spectral characterization of T-shape trees
• Spectral determination of graphs whose components are paths and cycles
• The complement of the path is determined by its spectrum
• The lollipop graph is determined by its spectrum
• Which graphs are determined by their spectrum?

Cited in

(36)

• The characterization of graphs with eigenvalue -1 of multiplicity n-4 or n-5
• Spectral characterization of the complete graph removing a cycle
• Adjacent spectral characterization of complete bipartite graphs
• On the second largest \(A_{\alpha}\)-eigenvalues of graphs
• Graphs determined by signless Laplacian spectra
• Per-spectral and adjacency spectral characterizations of a complete graph removing six edges
• Complete split graph determined by its (signless) Laplacian spectrum
• The characterizing properties of (signless) Laplacian permanental polynomials of almost complete graphs
• \( A_\alpha\)-spectral characterizations of some joins
• On the spectral characterizations of graphs
• The signed graphs with all but at most three eigenvalues equal to \(-1\)
• Majorization, degree sequence and \(A_\alpha\)-spectral characterization of graphs
• Gaussianization of the spectra of graphs and networks. Theory and applications
• On the spectral characterization of mixed extensions of P₃
• The kite graph is determined by its adjacency spectrum
• On the spectral characterization of kite graphs
• Graphs with eigenvalue \(-1\) of multiplicity \(2 \theta (G)+ \rho (G) -1\)
• Per-spectral characterizations of some bipartite graphs
• Some graphs determined by their distance spectrum
• On the spectral characterization of pineapple graphs
• The signless Laplacian spectral radius of some strongly connected digraphs
• Extremal spectral radius of nonregular graphs with prescribed maximum degree
• \(A_\alpha\) and \(L_\alpha\)-spectral properties of spider graphs
• Spectral characterization of the complete graph removing a path
• Spectral characterization of families of split graphs
• The multiplicity of \(-2\) as an eigenvalue of the distance matrix of graphs
• Spectral characterizations of two families of nearly complete bipartite graphs
• Spectral characterization of the complete graph removing a path: completing the proof of Cámara-Haemers conjecture
• Spectral characterization of the complete graph removing a path of small length
• scientific article; zbMATH DE number 7335987 (Why is no real title available?)
• Spectral and combinatorial properties of some algebraically defined graphs
• A note on non-\(\mathbb{R}\)-cospectral graphs
• New families of graphs determined by their generalized spectrum
• On the eigenvalues of eccentricity matrix of graphs
• Some graphs determined by their signless Laplacian (distance) spectra
• On claw-free graphs with all but four eigenvalues equal to \(0\) or \(-1\)

This page was built for publication: Spectral characterizations of almost complete graphs

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