Connected irregular cospectral graphs with distinct Lovász numbers

Abstract

For every integer n ≥ 11, we construct connected, irregular, nonisomorphic graphs on n vertices with equal adjacency, Laplacian, signless Laplacian, normalized Laplacian, and Seidel spectra and equal independence, clique, chromatic, complement chromatic, and maximum-cut numbers, but distinct Lovász ϑ-numbers. We join each graph in a fixed cospectral, nonisomorphic regular pair on ten vertices, due to van Dam and Haemers (2003), with K_n−10. We prove that these joins preserve equality of the five spectra and stated integer-valued invariants, and leave the respective Lovász numbers unchanged. We derive exact expressions for these numbers and prove that they are distinct. We also determine the cardinality-constrained maximum-cut profiles of both base graphs and their complements, yielding exact formulas and equality of maximum-cut numbers for the joins of either the base graphs or their complements with K_n−10. For n=10, we present a regular pair satisfying all stated properties except irregularity, followed by a connected, irregular, nonisomorphic pair satisfying all properties. An exhaustive computer search finds no connected, irregular, nonisomorphic pair on at most nine vertices sharing the first four spectra and all stated integer-valued invariants. Thus, ten is the smallest possible order, and such pairs exist for every n ≥ 10. This extends and strengthens Sason's (2024) result for \emph{even} n ≥ 14, which used the neighbors splitting join operation and did not address Seidel matrices, complement chromatic numbers, or maximum-cut numbers of the graphs or joins of their complements. Thus, the Lovász number efficiently certifies nonisomorphism even when all five spectra and stated integer-valued invariants coincide.

On the generalized cospectral mates of chain graphs of rank 4
Wei Wang, Siqi Wu
arXiv13 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
On the invariance of irregular Hodge numbers under crepant birational equivalences
Yichen Qin
arXiv2 Sep 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
Stringy Irregular Hodge Numbers for Non-Simplicial Toric Landau--Ginzburg Data
Haoxu Wang
arXiv1 Sep 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
On the existence of F-irregular graphs for disconnected graphs F
Tatiana Dovzhenok
arXiv13 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
A short note on K_n-irregular graphs
Tatiana Dovzhenok
arXiv24 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{sason2026connected,
  title = {{Connected irregular cospectral graphs with distinct Lovász numbers}},
  author = {Igal Sason},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.10884},
  eprint = {2609.10884},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.10884},
}

RIS

TY  - UNPB
TI  - Connected irregular cospectral graphs with distinct Lovász numbers
AU  - Igal Sason
PY  - 2026
DA  - 2026/10/22
PB  - arXiv
DO  - 10.48550/arxiv.2609.10884
UR  - https://arxiv.org/abs/2609.10884
AB  - For every integer n ≥ 11, we construct connected, irregular, nonisomorphic graphs on n vertices with equal adjacency, Laplacian, signless Laplacian, normalized Laplacian, and Seidel spectra and equal independence, clique, chromatic, complement chromatic, and maximum-cut numbers, but distinct Lovász ϑ-numbers. We join each graph in a fixed cospectral, nonisomorphic regular pair on ten vertices, due to van Dam and Haemers (2003), with K_n−10. We prove that these joins preserve equality of the five spectra and stated integer-valued invariants, and leave the respective Lovász numbers unchanged. We derive exact expressions for these numbers and prove that they are distinct. We also determine the cardinality-constrained maximum-cut profiles of both base graphs and their complements, yielding exact formulas and equality of maximum-cut numbers for the joins of either the base graphs or their complements with K_n−10. For n=10, we present a regular pair satisfying all stated properties except irregularity, followed by a connected, irregular, nonisomorphic pair satisfying all properties. An exhaustive computer search finds no connected, irregular, nonisomorphic pair on at most nine vertices sharing the first four spectra and all stated integer-valued invariants. Thus, ten is the smallest possible order, and such pairs exist for every n ≥ 10. This extends and strengthens Sason's (2024) result for \emph{even} n ≥ 14, which used the neighbors splitting join operation and did not address Seidel matrices, complement chromatic numbers, or maximum-cut numbers of the graphs or joins of their complements. Thus, the Lovász number efficiently certifies nonisomorphism even when all five spectra and stated integer-valued invariants coincide.
ER  -

Abstract

Related

Cite