Spectral characterization of the complete graph removing a path
Spectral characterization of the complete graph removing a path
复制标题
DOI：
10.1016/j.dam.2020.04.011
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Muhuo Liu;H. Shan;Xiaofeng Gu
中科院分区：
文献类型：
--
作者：
Muhuo Liu;H. Shan;Xiaofeng Gu
一个图G称为A − DS，如果每个具有相同邻接谱的图都同构于G。设Kn ∈ Pk是由n阶完全图Kn去掉k阶路Pk的所有边而得到的图. Doob和Haemers证明了Kn <$Pn是A-DS。2014年，卡马拉和海默斯猜想，对于任何2 ≤ k ≤ n，K n P k都是A − D S，并且他们成功地证明了对于2 ≤ k ≤ 6。最近，Mao，Cioabboutin和Wang证明了7 ≤ k ≤ 9的猜想。在本文中，我们证明了该猜想对所有k ≥ 20都成立。
A graph G is said to be A− D S if every graph having the same adjacency spectrum is isomorphic to G. Let K n∖ P k be the graph obtained from the complete graph K n with n vertices by removing all edges of a path P k with k vertices. It was shown by Doob and Haemers that K n∖ P n is A− D S. In 2014, Cámara and Haemers conjectured that K n∖ P k is A− D S for every 2≤ k≤ n, and they succeeded in proving it for 2≤ k≤ 6. Recently, Mao, Cioabă and Wang verified the conjecture for 7≤ k≤ 9. In this paper, we show that the conjecture is true for all k≥ 20.