Connected irregular cospectral graphs with identical combinatorial invariants and distinct Lovász numbers

Abstract

For every integer $n\ge 11$, we construct pairs of connected, irregular, nonisomorphic graphs on $n$ vertices that are cospectral for the adjacency, Laplacian, signless Laplacian, normalized Laplacian, and Seidel matrices, have equal independence, clique, chromatic, complement chromatic, and maximum-cut numbers, and have distinct Lovász $\vartheta$-numbers. Each pair is formed by joining $K_{n-10}$ to fixed cospectral, nonisomorphic, regular graphs on ten vertices due to van Dam and Haemers. We prove that the joins retain equality of the five spectra and listed integer-valued invariants, while preserving the respective Lovász numbers. We derive exact formulas for these numbers and prove them distinct. We also determine the cardinality-constrained maximum-cut profiles of the base graphs and their complements. They give exact formulas and prove equality of the maximum-cut numbers within each pair, both for the joins of the base graphs with $K_{n-10}$ and for those of their complements with $K_{n-10}$. For $n=10$, we first give a regular pair with all the stated properties except irregularity, then a connected, irregular, nonisomorphic pair sharing all five spectra and listed integer-valued invariants but having distinct Lovász numbers. An exhaustive SageMath computation shows that no connected, irregular, nonisomorphic pair on at most nine vertices shares all five spectra and listed integer-valued invariants. Thus, ten is the smallest possible order, and such pairs exist for every $n\ge 10$. It extends and strengthens a result for even $n\ge 14$ (Sason, '24), which did not address Seidel matrices, complement chromatic numbers, maximum-cut numbers of the graphs, or those of the corresponding joins formed from their complements. Thus, the Lovász number is a computable certificate of nonisomorphism even when all five spectra and listed integer-valued invariants coincide.

The results have been strengthened, followed by more editing