Tight bounds for generalized power domination in regular graphs

Abstract

Dorbec et al. [SIAM J. Discrete Math., 27 (2013)] conjectured that, for all integers $k\ge 1$ and $r\ge 3$, every connected $r$-regular graph $G$ of order $n$, other than $K_{r,r}$, satisfies ${\gamma }_{P,k}(G)\le n/(r+1)$. After disproving this conjecture, Chen et al.[Graphs Combin., 38 (2022)] proposed a corresponding conjecture for claw-free regular graphs. In this paper, we prove this conjecture: for integers $k\ge \ell \ge 1$, every connected claw-free $(k+\ell +1)$-regular graph $G$ of order $n$ satisfies ${\gamma }_{P,k}(G)\le n/(k+\ell +2)$, and this bound is tight. Moreover, without the claw-free assumption, we show that, for each fixed integer $k\ge 1$, the supremum of ${\gamma }_{P,k}(G)/|V(G)|$ over all connected $r$-regular graphs $G$ is asymptotic to $(\ln r)/r$ as $r\to \infty$.