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

Source abstract

For every integer $n \geq 11$, we construct a pair of connected, irregular, nonisomorphic graphs, each on $n$ vertices, that are cospectral with respect to the adjacency, Laplacian, signless Laplacian, and normalized Laplacian matrices and have the same independence number, clique number, chromatic number, and chromatic number of their complements, but have distinct Lovász $\vartheta$-numbers that are independent of $n$. For $n=10$, we first exhibit a regular pair satisfying the analogous conditions. Our construction takes the ordinary join of each member of this fixed regular pair on ten vertices with a complete graph, thereby preserving simultaneous cospectrality with respect to all four matrices, as well as the respective Lovász numbers. We derive exact analytic expressions for these Lovász numbers and prove that they are distinct, without relying on numerical approximations. An exhaustive search shows that no pair of connected, irregular, nonisomorphic graphs on fewer than ten vertices is simultaneously cospectral with respect to the four matrices while also having identical values of the four listed combinatorial invariants. Moreover, the search produces a pair of connected, irregular, nonisomorphic graphs on ten vertices satisfying all these conditions and having distinct Lovász $\vartheta$-numbers. Consequently, the smallest order for which such a pair of connected, irregular graphs exists is exactly 10, and such a pair exists for every $n \geq 10$. This strengthens an earlier existence result for all even orders $n \geq 14$ (Sason, 2024). Beyond its role in bounding the Shannon capacity and other combinatorial graph invariants, the Lovász number thus provides an efficiently computable certificate of nonisomorphism for a family of graph pairs that cannot be distinguished by the four spectra or the four listed invariants.