Constructing families of cospectral regular graphs

DOI10.1017/S096354832000019XzbMATH Open1462.05226arXiv2110.04985OpenAlexW3040425675MaRDI QIDQ4987254FDOQ4987254

Authors: Michael Haythorpe, Alex Newcombe 

Publication date: 30 April 2021

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: A set of graphs are called cospectral if their adjacency matrices have the same characteristic polynomial. In this paper we introduce a simple method for constructing infinite families of cospectral regular graphs. The construction is valid for special cases of a property introduced by Schwenk. For the case of cubic (3-regular) graphs, computational results are given which show that the construction generates a large proportion of the cubic graphs, which are cospectral with another cubic graph.

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

Recommendations

• Construction of cospectral regular graphs
• Large families of cospectral graphs
• Construction of cospectral integral regular graphs
• Construction of graphs with distinct eigenvalues
• Constructing cospectral graphs

zbMATH Keywords

infinite families of cospectral regular graphsremoval cospectral sets

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex degrees (05C07) Structural characterization of families of graphs (05C75)

Cites Work

• Eigenspaces of graphs
• Cospectral graphs and regular orthogonal matrices of level 2
• Constructing cospectral graphs
• Genetic theory for cubic graphs
• Cospectral regular graphs with and without a perfect matching
• Title not available (Why is that?)
• Hamiltonian cycle problem and Markov chains.
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (10)

• Graphs cospectral with Kneser graphs
• Finding singularly cospectral graphs
• Cospectral constructions for several graph matrices using cousin vertices
• Aα and Lα-spectral properties of spider graphs
• On adjacency and Laplacian cospectral non-isomorphic signed graphs
• Regularity and the generalized adjacency spectra of graphs
• Construction of cospectral graphs
• Constructing cospectral graphs
• Title not available (Why is that?)
• Large families of cospectral graphs

This page was built for publication: Constructing families of cospectral regular graphs

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