English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper provides new observations on the Lov\'{a}sz $\theta$-function ofgraphs. These include a simple closed-form expression of that function for allstrongly regular graphs, together with upper and lower bounds on that functionfor all regular graphs. These bounds are expressed in terms of thesecond-largest and smallest eigenvalues of the adjacency matrix of the regulargraph, together with sufficient conditions for equalities (the upper bound isdue to Lov\'{a}sz, followed by a new sufficient condition for its tightness).These results are shown to be useful in many ways, leading to the determinationof the exact value of the Shannon capacity of various graphs, eigenvalueinequalities, and bounds on the clique and chromatic numbers of graphs. Sincethe Lov\'{a}sz $\theta$-function factorizes for the strong product of graphs,the results are also particularly useful for parameters of strong products orstrong powers of graphs. Bounds on the smallest and second-largest eigenvaluesof strong products of regular graphs are consequently derived, expressed asfunctions of the Lov\'{a}sz $\theta$-function (or the smallest eigenvalue) ofeach factor. The resulting lower bound on the second-largest eigenvalue of a$k$-fold strong power of a regular graph is compared to the Alon--Boppanabound; under a certain condition, the new bound is superior in its exponentialgrowth rate (in $k$). Lower bounds on the chromatic number of strong productsof graphs are expressed in terms of the order and the Lov\'{a}sz$\theta$-function of each factor. The utility of these bounds is exemplified,leading in some cases to an exact determination of the chromatic numbers ofstrong products or strong powers of graphs. The present research paper is aimedto have tutorial value as well.

Observations on the Lov\'asz $\theta$-Function, Graph Capacity, Eigenvalues, and Strong Products