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

• A note on cospectral graphs
• Constructing cospectral graphs
• Cospectral graphs and the generalized adjacency matrix
• Developments on spectral characterizations of graphs
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 3394189 (Why is no real title available?)
• 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

(39)

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

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)