Connected irregular cospectral graphs with identical combinatorial invariants and distinct Lov\'{a}sz numbers

Abstract

For every integer $n\geq 11$, we construct pairs of connected, irregular, nonisomorphic graphs on $n$ vertices that are cospectral for the adjacency, Laplacian, signless Laplacian, and normalized Laplacian matrices, have equal independence, clique, chromatic, complement chromatic, and maximum-cut numbers, and have distinct Lov\'{a}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 (2003). We prove that the joins retain equality of the four spectra and listed integer-valued invariants, while preserving the respective Lov\'{a}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 four spectra and listed integer-valued invariants but having distinct Lov\'{a}sz numbers. An exhaustive SageMath computation shows that no connected, irregular, nonisomorphic pair on at most nine vertices shares all four spectra and listed integer-valued invariants. Thus, ten is the smallest possible order, and such pairs exist for every $n\geq 10$. This extends and strengthens a result for even $n\geq 14$ (Sason, 2024), which did not address complement chromatic numbers, the maximum-cut numbers of the graphs, or those of the corresponding joins formed from their complements. Thus, the Lov\'{a}sz number is an efficiently computable certificate of nonisomorphism even when all four spectra and listed integer-valued invariants coincide.