Vizing-type bounds for graphs with induced subgraph restrictions

Abstract

For any graphs $G$ and $H$, we say that a bound is of Vizing-type if $\gamma (G\square H)\ge c\gamma (G)\gamma (H)$ for some constant $c$. We show several bounds of Vizing-type for graphs $G$ with forbidden induced subgraphs. In particular, if $G$ is a triangle and $K_{1,r}$-free graph, then for any graph $H$, $\gamma (G\square H)\ge \frac{r}{2r-1}\gamma (G)\gamma (H)$. If $G$ is a $K_r$ and $P_5$-free graph for some integer $r\ge 2$, then for any graph $H$, $\gamma (G\square H)\ge \frac{r-1}{2r-3}\gamma (G)\gamma (H)$. We do this by bounding the power of $G$, $\pi (G)$. We show that if $G$ is claw-free and $P_6$-free or $K_4$ and $P_5$-free, then for any graph $H$, $\gamma (G\square H)\ge \gamma (G)\gamma (H)$. Furthermore, we show Vizing-type bounds in terms of the diameter of $G$.

9 pages