Spectral characterizations of almost complete graphs

2012/11/19 by Marc Cámara, Cámara, Marc, Willem H. Haemers +1 · 1 citation
Chemistry · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Synthesis and Properties of Aromatic Compounds

paper · pdf · doi:10.48550/arxiv.1211.4420

openalex publication_date 2012/11/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 m ≤ n-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.

Cited by

• Multiplicity Bounds for Arbitrary Eigenvalues of Connected Signed Graphs

Related

• Spectral characterizations of two families of nearly complete bipartite graphs
• Spectral characterization of the complete graph removing a path of small length
• Generalized Spectral Characterization of Graphs: Revisited
• A simple arithmetic criterion for graphs being determined by their generalized spectra
• A characterization of generalized cospectrality of rooted graphs with applications in graph reconstruction