Exponentially many graphs have a Q-cospectral mate

被引：7

作者：

Carvalho, Joao ^{[1
]}

Souza, Bruna S. ^{[1
]}

Trevisan, Vilmar ^{[1
]}

Tura, Fernando C. ^{[2
]}

机构：

[1] Univ Fed Rio Grande do Sul, Inst Matemat, BR-91509900 Porto Alegre, RS, Brazil

[2] Univ Fed Santa Maria, Dept Matemat, BR-97105900 Santa Maria, RS, Brazil

来源：

DISCRETE MATHEMATICS | 2017年 / 340卷 / 09期

关键词：

Cospectral graphs; Signless Laplacian matrix; Threshold graph; SIGNLESS LAPLACIAN; SPECTRAL THEORY;

D O I：

10.1016/j.disc.2017.04.009

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We develop an algorithm for computing the characteristic polynomial of matrices related to threshold graphs. We use this as tool to exhibit, for any natural number n >= 4, 2(n-4) graphs with n vertices that have a non isomorphic pair with the same signless Laplacian spectrum. We also show how to construct infinite families of pairs of non isomorphic graphs having the same Q-spectrum. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：2079 / 2085

页数：7

共 17 条

[1] Connected graphs of fixed order and size with maximal Q-index: Some spectral bounds [J].

Andelic, Milica ;

da Fonseca, Carlos M. ;

Simic, Slobodan K. ;

Tosic, Dejan V. .

DISCRETE APPLIED MATHEMATICS, 2012, 160 (4-5) :448-459

[2]

[Anonymous], 2016, ARXIV151203547V2

[3]

Cvetkovi DM, 2008, BULLETIN, V137, P131

[4] Signless Laplacians of finite graphs [J].

Cvetkovic, Dragos ;

Rowlinson, Peter ;

Simic, Slobodan K. .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2007, 423 (01) :155-171

[5] TOWARDS A SPECTRAL THEORY OF GRAPHS BASED ON THE SIGNLESS LAPLACIAN, III [J].

Cvetkovic, Dragos ;

Simic, Slobodan K. .

APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2010, 4 (01) :156-166

[6] TOWARDS A SPECTRAL THEORY OF GRAPHS BASED ON THE SIGNLESS LAPLACIAN, I [J].

Cvetkovic, Dragos ;

Simic, Slobodan K. .

PUBLICATIONS DE L INSTITUT MATHEMATIQUE-BEOGRAD, 2009, 85 (99) :19-33

[7] Towards a spectral theory of graphs based on the signless Laplacian, II [J].

Cvetkovic, Dragos ;

Simic, Slobodan K. .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2010, 432 (09) :2257-2272

[8]

Godsil C., 1976, Proceedings of the 4th Australian Conference on Combinatorial Mathematics, P73

[9]

Godsil C. D., 1982, Aequationes Math, V25, P257, DOI [DOI 10.1007/BF02189621, 10.1007/BF02189621]

[10] Enumeration of cospectral graphs [J].

Haemers, WH ;

Spence, E .

EUROPEAN JOURNAL OF COMBINATORICS, 2004, 25 (02) :199-211

← 1 2 →