Spectral characterization of the complete graph removing a cycle

被引：1

作者：

Liu, Muhuo ^{[1
]}

Gu, Xiaofeng ^{[2
]}

Shan, Haiying ^{[3
]}

Stanic, Zoran ^{[4
]}

机构：

[1] South China Agr Univ, Dept Math, Guangzhou 510642, Peoples R China

[2] Univ West Georgia, Dept Comp & Math, Carrollton, GA 30118 USA

[3] Tongji Univ, Sch Math Sci, Key Lab Intelligent Comp & Applicat, Minist Educ, Shanghai 200092, Peoples R China

[4] Univ Belgrade, Fac Math, Belgrade 11000, Serbia

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES A | 2024年 / 205卷

基金：

中国国家自然科学基金;

关键词：

Adjacency matrix; Spectral determination; Complete graph; Cycle; Unicyclic graph; Tree; 2ND LARGEST EIGENVALUE; PATH;

D O I：

10.1016/j.jcta.2024.105868

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A graph is determined by its spectrum if there is not another graph with the same spectrum. Camara and Haemers proved that the graph Kn \ Ck, obtained from the complete graph Kn with n vertices by deleting all edges of a cycle Ck with k vertices, is determined by its spectrum for k is an element of {3, 4, 5}, but not for k = 6. In this paper, we show that k = 6 is the unique exception for the spectral determination of Kn \ Ck. (c) 2024 Elsevier Inc. All rights reserved.

引用

页数：46

共 29 条

[1] [Anonymous], 2010, An Introduction to the Theory of Graph Spectra, DOI DOI 10.1017/CBO9780511801518
[2] Brouwer AE, 2012, UNIVERSITEXT, P1, DOI 10.1007/978-1-4614-1939-6
[3] Spectral characterizations of almost complete graphs
Camara, Marc
Haemers, Willem H.
[J]. DISCRETE APPLIED MATHEMATICS, 2014, 176 : 19 - 23
[4] On the nullity of graphs
Cheng, Bo
Liu, Bolian
[J]. ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2007, 16 : 60 - 67
[5] Graphs with three eigenvalues and second largest eigenvalue at most 1
Cheng, Xi-Ming
Greaves, Gary R. W.
Koolen, Jack H.
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2018, 129 : 55 - 78
[6] The complement of the path is determined by its spectrum
Doob, M
Haemers, WH
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2002, 356 (1-3) : 57 - 65
[7] Dragos Cvetkovic:., 1982, Publications de l'Institut mathematique (Beograd), Nouvelle serie, V31, P15
[8] On generalized θ-graphs whose second largest eigenvalue does not exceed 1
Gao, Mingfei
Huang, Qiongxiang
[J]. DISCRETE MATHEMATICS, 2008, 308 (23) : 5849 - 5855
[9] On bicyclic graphs whose second largest eigenvalue does not exceed 1
Guo, SG
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2005, 407 : 201 - 210
[10] INTERLACING EIGENVALUES AND GRAPHS
HAEMERS, WH
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 1995, 226 : 593 - 616

← 1 2 3 →