Spectral characterizations of almost complete graphs

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

Willem H. Haemers, Marc Cámara

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

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Spectral determination of graphs whose components are paths and cycles
• On the generalized spectral characterization of graphs having an isolated vertex

Cited In (33)

• Graphs determined by signless Laplacian spectra
• 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
• The kite graph is determined by its adjacency spectrum
• Aα and Lα-spectral properties of spider graphs
• Graphs with eigenvalue \(-1\) of multiplicity \(2 \theta (G)+ \rho (G) -1\)
• The multiplicity of -2 as an eigenvalue of the distance matrix of 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
• Title not available (Why is that?)
• Spectral characterization of the complete graph removing a path
• Spectral characterization of families of split graphs
• Spectral characterization of the complete graph removing a path: completing the proof of Cámara-Haemers conjecture
• On the spectral characterization of Kite graphs
• 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
• Title not available (Why is that?)
• 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)