The Ultimate Categorical Independence Ratio of a Graph
Authors:
- Jason I. BrownJBJason I. Brown
- Richard J. NowakowskiRNRichard J. Nowakowski
- Douglas RallDRDouglas Rall
- 1 May 1996
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 9 (2) , 290-300
Abstract
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.
Keywords
This publication has 12 references indexed in Scilit:
- Independence ratios of graph powersDiscrete Mathematics, 1994
- On the chromatic number of the product of graphsJournal of Graph Theory, 1985
- The chromatic number of the product of two 4-chromatic graphs is 4Combinatorica, 1985
- Analogues of the Shannon Capacity of a Graph1982
- ON THE MOBILE RADIO FREQUENCY ASSIGNMENT PROBLEM AND THE TRAFFIC LIGHT PHASING PROBLEMAnnals of the New York Academy of Sciences, 1979
- On the Shannon capacity of a graphIEEE Transactions on Information Theory, 1979
- Graph Theory and Its Applications to Problems of Society1978
- The chromatic number and other functions of the lexicographic productJournal of Combinatorial Theory, Series B, 1975
- A (<5)-Colour Theorem for Planar GraphsBulletin of the London Mathematical Society, 1973
- On a problem of C. E. Shannon in graph theoryProceedings of the American Mathematical Society, 1967