Large induced distance matchings in certain sparse random graphs

For a fixed integer $k\geqslant 2$, let $G\in \mathcal{G}(n,p)$ be a simple connected graph on $n\rightarrow\infty$ vertices with the expected degree $d=np$ satisfying $d\geqslant c$ and $d^{k-1}= o(n)$ for some large enough constant $c$. We show that the asymptotical size of any maximal collection of edges $M$ in $G$ such that no two edges in $M$ are within distance $k$, which is called a distance $k$-matching, is between $\frac{(k-1)n\log d}{4d^{k-1}}$ and $\frac{k n \log d}{2d^{k-1}}$. We also design a randomized greedy algorithm to generate one large distance $k$-matching in $G$ with asymptotical size $\frac{kn\log d}{4d^{k-1}}$. Our results partially generalize the results on the size of the largest distance $k$-matchings from the case $k=2$ or $d=c$ for some large constant $c$.

No reviews yet.

No comments yet.