On the Ratio of Shannon Numbers of Graphs

Abstract

Let $\Gamma$ be a function that maps two arbitrary graphs $G$ and $H$ to a non-negative real number such that $$\alpha (G^{⊠n})\le \alpha (H^{⊠n})\Gamma (G,H{)}^n$$ where $n$ is any natural number and $G^{⊠n}$ is the strong product of $G$ with itself $n$ times. We establish the equivalence of two different approaches for finding such a function $\Gamma$. The common solution obtained through either approach is termed ``the relative fractional independence number of a graph $G$ with respect to another graph $H$". We show this function by ${\alpha }^{\ast }(G|H)$ and discuss some of its properties. In particular, we show that ${\alpha }^{\ast }(G|H)\ge \frac{X(G)}{X(H)}\ge \frac{1}{{\alpha }^{\ast }(H|G)},$ where $X(G)$ can be the independence number, the Shannon capacity, the fractional independence number, the Lovász number, or the Schrijver's or Szegedy's variants of the Lovász number of a graph $G$. This inequality is the first explicit non-trivial upper bound on the ratio of the invariants of two arbitrary graphs, as mentioned earlier, which can also be used to obtain upper or lower bounds for these invariants. As explicit applications, we present new upper bounds for the ratio of the Shannon capacity of two Cayley graphs and compute new lower bounds on the Shannon capacity of certain Johnson graphs (yielding the exact value of their Haemers number). Moreover, we show that ${\alpha }^{\ast }(G|H)$ can be used to present a stronger version of the well-known No-Homomorphism Lemma.

Cited by in corpus (1)

• Observations on Graph Invariants with the Lovász $\vartheta$-Function