Spectral characterizations of almost complete graphs

DOI10.1016/J.DAM.2013.08.002zbMATH Open1298.05233arXiv1211.4420OpenAlexW2018398584MaRDI QIDQ403557FDOQ403557

Authors: Marc Cámara, Willem H. Haemers 

Publication date: 29 August 2014

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

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.

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

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

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)

Cites Work

• Developments on spectral characterizations of graphs
• A note on cospectral graphs
• Which graphs are determined by their spectrum?
• On the spectral characterization of T-shape trees
• Constructing cospectral graphs
• Cospectral graphs and the generalized adjacency matrix
• The lollipop graph is determined by its spectrum
• The complement of the path is determined by its spectrum
• Title not available (Why is that?)
• Title not available (Why is that?)
• Spectral determination of graphs whose components are paths and cycles
• On the generalized spectral characterization of graphs having an isolated vertex

Cited In (36)

• Graphs determined by signless Laplacian spectra
• Adjacent spectral characterization of complete bipartite graphs
• On the second largest \(A_{\alpha}\)-eigenvalues of graphs
• 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
• On the spectral characterization of mixed extensions of \(P_3\)
• Gaussianization of the spectra of graphs and networks. Theory and applications
• On the spectral characterization of kite graphs
• The kite graph is determined by its adjacency spectrum
• Graphs with eigenvalue \(-1\) of multiplicity \(2 \theta (G)+ \rho (G) -1\)
• Some graphs determined by their distance spectrum
• Per-spectral characterizations of some bipartite graphs
• 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
• The multiplicity of \(-2\) as an eigenvalue of the distance matrix of graphs
• Spectral characterization of families of split 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
• Title not available (Why is that?)
• Spectral and combinatorial properties of some algebraically defined graphs
• A note on non-\(\mathbb{R}\)-cospectral graphs
• Some graphs determined by their signless Laplacian (distance) spectra
• New families of graphs determined by their generalized spectrum
• On claw-free graphs with all but four eigenvalues equal to \(0\) or \(-1\)
• On the eigenvalues of eccentricity matrix of graphs
• The characterization of graphs with eigenvalue -1 of multiplicity n-4 or n-5
• Spectral characterization of the complete graph removing a cycle

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)