Domination versus edge domination

Abstract

We propose the conjecture that the domination number $\gamma (G)$ of a $\Delta$-regular graph $G$ with $\Delta \ge 1$ is always at most its edge domination number ${\gamma }_e(G)$, which coincides with the domination number of its line graph. We prove that $\gamma (G)\le \left(1+\frac{2(\Delta -1)}{\Delta 2^{\Delta }}\right){\gamma }_e(G)$ for general $\Delta \ge 1$, and $\gamma (G)\le \left(\frac{7}{6}-\frac{1}{204}\right){\gamma }_e(G)$ for $\Delta =3$. Furthermore, we verify our conjecture for cubic claw-free graphs.