On the $b$-Independence Number of Sparse Random Graphs

Abstract

Let graph $G=(V,E)$ and integer $b\geq 1$ be given. A set $S\subseteq V$ is said to be $b$-independent if $u,v\in S$ implies $d_G(u,v)>b$, where $d_G(u,v)$ is the shortest distance between $u$ and $v$ in $G$. The $b$-independence number $\a_b(G)$ is the size of the largest $b$-independent subset of $G$. When $b=1$ this reduces to the standard definition of independence number.

We study this parameter in relation to the random graph $G_{n,p},\,p=d/n$, in particular, when $d$ is a large constant. We show that w.h.p. if $d\geq d_{\epsilon, b}$, $$ \left| \alpha_b(G_{n,p}) - \frac{2bn}{d^b} \biggl(\log{d} - \frac{\log{\log{d}}}{b} - \frac{\log{2b}}{b} + \frac{1}{b}\biggr)\right| \leq \frac{\epsilon n}{d^b}.$$