Cospectral regular graphs with and without a perfect matching

DOI10.1016/J.DISC.2014.11.002MaRDI QIDQ482228zbMATHOpenAlexFDO

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 graphsperfect matchingGodsil-McKay switching

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

(13)

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

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)