Observations on the Lovász θ-Function, Graph Capacity, Eigenvalues, and Strong Products †

Area of Science:

• Graph Theory
• Spectral Graph Theory
• Combinatorial Optimization

Background:

• The Lovász θ-function is a fundamental quantity in graph theory with applications in various combinatorial problems.
• Existing bounds for the Lovász θ-function often rely on eigenvalues of the adjacency matrix.
• Understanding the behavior of the Lovász θ-function for graph products is crucial for analyzing complex graph structures.

Purpose of the Study:

• To derive a simple closed-form expression for the Lovász θ-function for strongly regular graphs.
• To establish new upper and lower bounds for the Lovász θ-function of regular graphs using eigenvalues.
• To explore the applications of these new results in determining Shannon capacity, eigenvalue inequalities, and bounds on clique and chromatic numbers.

Main Methods:

• Derivation of a closed-form expression for the Lovász θ-function for strongly regular graphs.
• Development of new upper and lower bounds based on the smallest and second-largest eigenvalues of the adjacency matrix.
• Analysis of the Lovász θ-function's factorization property for the strong product of graphs.

Main Results:

• A simple closed-form expression for the Lovász θ-function is provided for all strongly regular graphs.
• New upper and lower bounds for the Lovász θ-function of regular graphs are established, linked to graph eigenvalues.
• The results yield exact values for Shannon capacity and bounds for clique and chromatic numbers, and improve bounds for strong graph products and powers.

Conclusions:

• The derived bounds and expressions offer significant advancements in understanding graph properties and capacities.
• The findings are particularly impactful for analyzing strong products and powers of graphs, offering superior bounds compared to existing methods.
• This research provides valuable insights and tools for both theoretical graph analysis and practical applications.