Spectral characterizations of almost complete graphs

被引：35

作者：

Camara, Marc ^{[1
]}

Haemers, Willem H. ^{[1
]}

机构：

[1] Tilburg Univ, NL-5000 LE Tilburg, Netherlands

来源：

DISCRETE APPLIED MATHEMATICS | 2014年 / 176卷

关键词：

Graph spectrum; Spectral characterization; Cospectral graphs;

D O I：

10.1016/j.dam.2013.08.002

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We investigate when a complete graph K, 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 Km 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 Km provided that n is big enough. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：19 / 23

页数：5

共 12 条

[1]

Boulet R, 2008, ELECTRON J COMB, V15

[2] Spectral determination of graphs whose components are paths and cycles [J].