Abstract:
This talk is focused on observations on the Lovász theta-function and capacity of graphs. These include a simple closed-form expression of that function for all strongly regular graphs, together with upper and lower bounds on that function for all regular graphs. These bounds are expressed in terms of the second-largest and smallest eigenvalues of the adjacency matrix of the regular graph, together with sufficient conditions for equalities (the upper bound is due to Lovász, followed by a new sufficient condition for its tightness). These results are shown to be useful in many ways, leading to the determination of the exact value of the Shannon capacity of some graphs, eigenvalue inequalities, and bounds on the clique and chromatic numbers of graphs.
The utility of these bounds is exemplified, leading in some cases to an exact determination of the chromatic numbers of strong products or strong powers of graphs. The published version of this work as a journal paper appears in https://doi.org/10.3390/e25010104.