Cospectral regular graphs with and without a perfect matching

Zolt\'{a}n L. Bl\'{a}zsik
Department of Computer Science, E\"{o}tv\"{o}s University, Hungary

Willem H. Haemers
Department of Econometrics and O.R., Tilburg University, Netherlands

Jay Cummings
Department of Mathematics, University of California, San Diego, USA

PDF

Minisymposium: SPECTRAL GRAPH THEORY

Content: At the 22nd British Combinatorial Conference Prof. Willem H. Haemers posed a question if there exists a pair of cospectral $d$-regular graphs, where one has a perfect matching and the other one not. We solved this question by finding a family of such pair of graphs for $d\ge 5$ using the Godsil-McKay switching argument. I would like to show you the construction and speak about the case of $d=2,3,4$ with some related questions.

Back to all abstracts