Chain graphs are not spectrally determined

Two non isomorphic graphs G and H are said to be cospectral, if they share the same adjacency eigenvalues. In this paper, we use a recursive procedure for computing the characteristic polynomial of chain graphs in order to obtain infinitely many pairs of connected cospectral chain graphs. This result disproves a conjecture posed in [Czechoslovak Math. J. 70 (4) (2020), 1125-1138]. In addition we construct infinite families of bipartite graphs sharing the same spectrum.

Authors

Institutions

Publication Details

Journal
Filomat
Published
2025-01-01
DOI
https://doi.org/10.2298/fil2507171a
Primary Topic
Graph theory and applications
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Chain graphs are not spectrally determined

Milica Anđelić, Fernando Tura
Filomat
Graph theory and applications
article

Chain graphs are not spectrally determined

Milica Anđelić, Fernando Tura
article en

Abstract

Two non isomorphic graphs G and H are said to be cospectral, if they share the same adjacency eigenvalues. In this paper, we use a recursive procedure for computing the characteristic polynomial of chain graphs in order to obtain infinitely many pairs of connected cospectral chain graphs. This result disproves a conjecture posed in [Czechoslovak Math. J. 70 (4) (2020), 1125-1138]. In addition we construct infinite families of bipartite graphs sharing the same spectrum.

FilomatVol. 39(7)
Universidade Federal de Santa Maria (BR), Kuwait University (KW)
Georgia State University, Conselho Nacional de Desenvolvimento Científico e Tecnológico, Universidade Federal de Santa Maria
Openalex Percentile: Top 74%
Graph theory and applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.