Irregular Cospectral Graphs with Distinct Lovász Numbers

For every integer n≥11, we construct a pair of connected, irregular, nonisomorphic graphs on n vertices that are cospectral with respect to the adjacency, Laplacian, signless Laplacian, normalized Laplacian, and Seidel matrices and have equal independence, clique, chromatic, complement chromatic, and maximum-cut numbers, but distinct Lovász ϑ-numbers. The graphs are obtained by joining each member of a fixed pair of cospectral, nonisomorphic regular graphs on ten vertices, constructed by van Dam and Haemers, with the complete graph Kn−10. We prove that this construction preserves the equality of the five spectra and the stated integer-valued combinatorial invariants within each pair, while leaving the respective Lovász numbers unchanged. We derive exact formulas for these Lovász numbers and prove that they are distinct. We also determine the cardinality-constrained maximum-cut profiles of the two base graphs and their complements. These profiles yield exact formulas and establish equality of the maximum-cut numbers within each pair, both for the joins of the base graphs with Kn−10 and for the joins of their complements with Kn−10. For n=10, we first present a regular pair satisfying all the stated properties except irregularity, and then a connected, irregular, nonisomorphic pair that shares all five spectra and all the stated integer-valued combinatorial invariants, but has distinct Lovász numbers. An exhaustive computer search shows that no pair of connected, irregular, nonisomorphic graphs on at most nine vertices shares the first four spectra and all the stated integer-valued combinatorial invariants. Hence, ten is the smallest possible order, and pairs with all the stated properties exist for every n≥10. This extends and strengthens an earlier result of the author for evenn≥14, which used the neighbors splitting join operation and did not address Seidel matrices, complement chromatic numbers, the maximum-cut numbers of the graphs, or the maximum-cut numbers of the corresponding joins formed from their complements. Thus, the Lovász number provides an efficiently computable certificate of nonisomorphism even when the five spectra and all the stated integer-valued combinatorial invariants coincide.