Constructing families of cospectral regular graphs

DOI10.1017/S096354832000019XMaRDI QIDQ4987254zbMATH OpenOpenAlexFDO

Authors Michael Haythorpe, Alex Newcombe

Publication date 30 April 2021

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

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

zbMATH Keywords

infinite families of cospectral regular graphsremoval cospectral sets

Mathematics Subject Classification ID

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

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.

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

Cites work

• Constructing cospectral graphs
• Construction of cospectral regular graphs
• Cospectral graphs and regular orthogonal matrices of level 2
• Cospectral regular graphs with and without a perfect matching
• Eigenspaces of graphs
• Genetic theory for cubic graphs
• Hamiltonian cycle problem and Markov chains.
• scientific article; zbMATH DE number 5125630 (Why is no real title available?)
• scientific article; zbMATH DE number 3655975 (Why is no real title available?)

Cited in

(19)

• Constructing graphs which are permanental cospectral and adjacency cospectral
• The smallest pair of cospectral cubic graphs with different chromatic indexes
• Constructing cospectral graphs via regular rational orthogonal matrices with level two
• Construction of cospectral graphs
• Cospectral constructions for several graph matrices using cousin vertices
• Construction of cospectral integral regular graphs
• Regularity and the generalized adjacency spectra of graphs
• Constructing cospectral graphs
• Graphs cospectral with Kneser graphs
• scientific article; zbMATH DE number 3841907 (Why is no real title available?)
• Cospectral regular graphs with and without a perfect matching
• Construction of graphs with distinct eigenvalues
• Constructions of cospectral graphs with different zero forcing numbers
• Construction of cospectral regular graphs
• A_ and L_-spectral properties of spider graphs
• On adjacency and Laplacian cospectral non-isomorphic signed graphs
• Large families of cospectral graphs
• Finding singularly cospectral graphs
• The A_-eigenvalues of the generalized subdivision graph

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)