The ultimate categorical independence ratio of a graph
SIAM Journal on Discrete Mathematics, 1996•SIAM
Let β(G) denote the independence number of a graph G. We introduce A(G)=k→∞β(G^k)/|V(
G)|^k, where the categorical graph product is used. This limit, surprisingly, lies in the range
(0,1/2∪{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)>β(G)/|V(G)|. This brings up the question; …
G)|^k, where the categorical graph product is used. This limit, surprisingly, lies in the range
(0,1/2∪{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)>β(G)/|V(G)|. This brings up the question; …
Let denote the independence number of a graph G. We introduce , where the categorical graph product is used. This limit, surprisingly, lies in the range . We can show that this limit can take any such rational number, but is there any G for which is irrational? A useful technique for bounding is to consider special spanning subgraphs. These bounds allow us to efficiently compute for many G. We give a condition which if true for G shows that . This brings up the question; for which G does ? 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.
Society for Industrial and Applied Mathematics以上显示的是最相近的搜索结果。 查看全部搜索结果