On the $b$ -Independence Number of Sparse Random Graphs (Q4819243)

Consider a graph \(G = (V, E)\). A subset \(S\) of \(V\) is said to be \(b\)-independent (where \(b\) is an integer at least 1) if \(u, v\in S\) implies \(d_G\) \((u, v) > b\), where \(d_G(u,v)\) is the least distance in the graph \(G\) between the vertices \(u, v\). The size of the largest \(b\)-independent subset of \(G\) is called its \(b\)-independence number and is denoted by \(\alpha_b(G)\). This paper is concerned with this parameter in relation to the random graphs \(G_{n,p}\) \((p =\frac dn\) when \(d\) is a largest constant). The main result of this paper is as follows: Let \(b\) be a positive integer constant and let \(\varepsilon > 0\) be given. Assume that \(d\) is a constant, greater than some fixed \(d_{e,b}\). Then with high probability we have \[ \left| \alpha_b(G_{n,p})-\frac{2bn}{d^b}\left(\log d -\frac{\log\log d}{b}-\frac{\log 2b}{b}+\frac 1b\right)\right|\leq \frac{\varepsilon n}{d^b}. \]