Cospectral regular graphs with and without a perfect matching

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.

• Publication year

  2014

• Venue

  Discrete Mathematics

• Publication date

  2014-09-02

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.disc.2014.11.002arXiv 1409.0630
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Research problems from the BCC22

  2011cited by this paper
• Regularity and the spectra of graphs

  2009cited by this paper
• Matchings in regular graphs from eigenvalues

  2009cited by this paper
• Eigenvalues and perfect matchings

  2005cited by this paper
• Which graphs are determined by their spectrum

  2003cited by this paper
• Constructing cospectral graphs

  1982influential reference

• On perfect matchings, edge-colourings and eigenvalues of cubic graphs

  2026cites this paper
• The edge-isoperimetric number of graphs and their powers: approaches from spectral graph theory, optimization and finite geometry

  2026cites this paper
• Propagation processes on (hyper)graphs: where zero forcing and burning meet

  2026cites this paper
• Counting cospectral graphs obtained via switching

  2025cites this paper
• Switching methods of level 2 for the construction of cospectral graphs

  2024cites this paper
• Constructing the r-uniform supertrees with the same spectral radius and matching energy

  2022cites this paper
• Constructing the Mate of Cospectral 5-regular Graphs with and without a Perfect Matching

  2022cites this paper
• On adjacency and Laplacian cospectral non-isomorphic signed graphs

  2022cites this paper
• The smallest pair of cospectral cubic graphs with different chromatic indexes

  2021cites this paper
• Factor-of-iid Schreier decorations of lattices in Euclidean spaces

  2021cites this paper
• Constructions of cospectral graphs with different zero forcing numbers

  2021cites this paper
• Generalized cospectral graphs with and without Hamiltonian cycles

  2020cites this paper
• Constructing families of cospectral regular graphs

  2020cites this paper
• Cospectral Bipartite Graphs with the Same Degree Sequences but with Different Number of Large Cycles

  2019cites this paper
• Cospectral Pairs of Regular Graphs with Different Connectivity

  2019cites this paper
• On NP-hard graph properties characterized by the spectrum

  2019cites this paper
• Graphs and finite geometries

  2019cites this paper
• Selected results in combinatorics and graph theory

  2016cites this paper
• Designs from Paley graphs and Peisert graphs

  2015cites this paper
• Switching methods for the construction of cospectral graphs ∗

  year unknowncites this paper