Abstract
Brown, Nowakowski and Rall defined the ultimate categorical independence ratio of a graph G as A(G)=\lim_{k\to \infty} i(G^{\times k}), where i(G)=\frac{α(G)}{|V(G)|} denotes the independence ratio of a graph G, and G^{\times k} is the k-th categorical power of G. Let a(G)=\max{\frac{|U|}{|U|+|N_G(U)|}: U is an independent set of G}}, where N_G(U) is the neighborhood of U in G. In this paper we answer a question of Alon and Lubetzky, namely we prove that if a(G)\le 1/2 then A(G)=a(G), and if a(G)>1/2 then A(G)=1. We also discuss some other open problems related to A(G) which are immediately settled by this result.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.