Cospectral regular graphs with and without a perfect matching

DOI10.1016/J.DISC.2014.11.002MaRDI QIDQ482228zbMATH OpenOpenAlexFDO

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

Publication date 19 December 2014

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

cospectral graphsGodsil-McKay switchingperfect matching

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(15)

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

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)