Cospectral regular graphs with and without a perfect matching

DOI10.1016/J.DISC.2014.11.002zbMATH Open1305.05186arXiv1409.0630OpenAlexW1990492407MaRDI QIDQ482228FDOQ482228

Authors: Zoltán Blázsik, Jay Cummings, Willem H. Haemers 

Publication date: 19 December 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: For each $bgeq5$ 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.

Full work available at URL: https://arxiv.org/abs/1409.0630

Recommendations

• Regularity and the spectra of graphs
• Construction of cospectral regular graphs
• Perfect matchings, eigenvalues and expansion
• Constructing families of cospectral regular graphs
• Matchings in regular graphs from eigenvalues

zbMATH Keywords

cospectral graphsperfect matchingGodsil-McKay switching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Which graphs are determined by their spectrum?
• Constructing cospectral graphs
• Matchings in regular graphs from eigenvalues
• Eigenvalues and perfect matchings
• Regularity and the spectra of graphs
• Research problems from the BCC22

Cited In (12)

• Graphs with at most one generalized cospectral mate
• Infinitely many pairs of cospectral integral regular graphs
• On NP-hard graph properties characterized by the spectrum
• On adjacency and Laplacian cospectral non-isomorphic signed graphs
• Constructing families of cospectral regular graphs
• Constructions of cospectral graphs with different zero forcing numbers
• Regularity and the generalized adjacency spectra of graphs
• Generalized cospectral graphs with and without Hamiltonian cycles
• Cospectral pairs of regular graphs with different connectivity
• Cospectral bipartite graphs with the same degree sequences but with different number of large cycles
• The smallest pair of cospectral cubic graphs with different chromatic indexes
• Regularity and the spectra of graphs

This page was built for publication: Cospectral regular graphs with and without a perfect matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q482228)