Cospectral regular graphs with and without a perfect matching

被引：10

作者：

Blazsik, Zoltan L. ^{[1
]}

Cummings, Jay ^{[2
]}

Haemers, Willem H. ^{[3
]}

机构：

[1] Eotvos Lorand Univ, Dept Comp Sci, Budapest, Hungary

[2] Univ Calif San Diego, Dept Math, San Diego, CA 92103 USA

[3] Tilburg Univ, Dept Econometr & OR, NL-5000 LE Tilburg, Netherlands

来源：

DISCRETE MATHEMATICS | 2015年 / 338卷 / 03期

关键词：

Perfect matching; Cospectral graphs; Godsil-McKay switching;

D O I：

10.1016/j.disc.2014.11.002

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

For each b >= 5 we construct a pair of cospectral b-regular graphs, where one has a perfect matching and the other one not. This solves a research problem posed by the third author at the 22nd British Combinatorial Conference. (C) 2014 Elsevier B.V. All rights reserved.

引用

页码：199 / 201

页数：3

共 6 条

[1] Eigenvalues and perfect matchings
Brouwer, AE
Haemers, WH
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2005, 395 : 155 - 162
[2] Research problems from the BCC22
Cameron, Peter J.
[J]. DISCRETE MATHEMATICS, 2011, 311 (13) : 1074 - 1083
[3] Matchings in regular graphs from eigenvalues
Cioaba, Sebastian M.
Gregory, David A.
Haemers, Willem H.
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2009, 99 (02) : 287 - 297
[4] Godsil C.D., 1982, Aequ. Math., V25, P257, DOI DOI 10.1007/BF02189621
[5] Haemers W.H., 2009, SURVEYS COMBINATORIC, V365 of, P75
[6] Which graphs are determined by their spectrum?
van Dam, ER
Haemers, WH
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2003, 373 : 241 - 272

← 1 →