The Ultimate Categorical Independence Ratio of a Graph
Jason I. Brown, Richard J. Nowakowski, Douglas F. Rall · SIAM Journal on Discrete Mathematics · 1996
Let $\beta (G)$ denote the independence number of a graph G. We introduce $A(G) = \lim_{k \to \infty } \beta (G^k )/| V(G) |^k $, where the categorical graph product is used. This limit, surprisingly, lies in the range $( 0,1/2 ] \cup \{ 1 \}$. We can show that this limit can take any such rational number, but is there any G for which $A(G)$ is irrational? A useful technique for bounding $A(G)$ is to consider special spanning subgraphs. These bounds allow us to efficiently compute $A(G)$ for many G. We give a condition which if true for G shows that $A(G) > \beta (G)/| V(G) |$. This brings up the question; for which G does $A(G) = \beta (G)/| V(G) |$? This happens if G is a Cayley graph of an Abelian group or if G is a connected graph that has an automorphism which has a single orbit.