AIMS Mathematics (Apr 2024)
Observations on graph invariants with the Lovász ϑ-function
Abstract
This paper delves into three research directions, leveraging the Lovász $ \vartheta $-function of a graph. First, it focuses on the Shannon capacity of graphs, providing new results that determine the capacity for two infinite subclasses of strongly regular graphs, and extending prior results. The second part explores cospectral and nonisomorphic graphs, drawing on a work by Berman and Hamud (2024), and it derives related properties of two types of joins of graphs. For every even integer such that $ n \geq 14 $, it is constructively proven that there exist connected, irregular, cospectral, and nonisomorphic graphs on $ n $ vertices, being jointly cospectral with respect to their adjacency, Laplacian, signless Laplacian, and normalized Laplacian matrices, while also sharing identical independence, clique, and chromatic numbers, but being distinguished by their Lovász $ \vartheta $-functions. The third part focuses on establishing bounds on graph invariants, particularly emphasizing strongly regular graphs and triangle-free graphs, and compares the tightness of these bounds to existing ones. The paper derives spectral upper and lower bounds on the vector and strict vector chromatic numbers of regular graphs, providing sufficient conditions for the attainability of these bounds. Exact closed-form expressions for the vector and strict vector chromatic numbers are derived for all strongly regular graphs and for all graphs that are vertex- and edge-transitive, demonstrating that these two types of chromatic numbers coincide for every such graph. This work resolves a query regarding the variant of the $ \vartheta $-function by Schrijver and the identical function by McEliece et al. (1978). It shows, by a counterexample, that the $ \vartheta $-function variant by Schrijver does not possess the property of the Lovász $ \vartheta $-function of forming an upper bound on the Shannon capacity of a graph. This research paper also serves as a tutorial of mutual interest in zero-error information theory and algebraic graph theory.
Keywords
