Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418308 | Discrete Applied Mathematics | 2014 | 5 Pages |
Abstract
We investigate when a complete graph KnKn 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 KmKm provided m≤n−2m≤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 KnKn, there is just one pair of nonisomorphic cospectral graphs. We construct nonisomorphic cospectral graphs (with cospectral complements) for all nn if six or more edges are deleted from KnKn, provided that nn is big enough.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Marc Cámara, Willem H. Haemers,