Cospectral pairs of regular graphs with different connectivity

DOI10.7151/DMGT.2278zbMATH Open1433.05195arXiv1904.05936OpenAlexW2997105615WikidataQ126431545 ScholiaQ126431545MaRDI QIDQ2296005FDOQ2296005

Willem H. Haemers

Publication date: 17 February 2020

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Abstract: For vertex and edge connectivity we construct infinitely many pairs of regular graphs with the same spectrum, but with different connectivity.

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

zbMATH Keywords

graph spectrumvertex connectivityspectral characterizationedge connectivity

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Connectivity (05C40)

Cites Work

• Title not available (Why is that?)
• Spectra of graphs
• An introduction to the theory of graph spectra
• Constructing cospectral graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Eigenvalues and edge-connectivity of regular graphs
• Cospectral regular graphs with and without a perfect matching
• Graphs cospectral with distance-regular graphs
• Distance-regularity and the spectrum of graphs
• Spectral Bounds for the Connectivity of Regular Graphs with Given Order

Cited In (8)

• The \(\alpha \)-spectral radius of general hypergraphs
• Infinitely many pairs of cospectral integral regular graphs
• Aα and Lα-spectral properties of spider graphs
• On NP-hard graph properties characterized by the spectrum
• Constructions of cospectral graphs with different zero forcing numbers
• The smallest pair of cospectral cubic graphs with different chromatic indexes
• Connected graphs cospectral with a friendship graph
• Aα spectra of graphs obtained by two corona operations and Aα cospectral graphs

This page was built for publication: Cospectral pairs of regular graphs with different connectivity

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