On a Vizing-type Integer Domination Conjecture

Abstract

Given a simple graph $G$, a dominating set in $G$ is a set of vertices $S$ such that every vertex not in $S$ has a neighbor in $S$. Denote the domination number, which is the size of any minimum dominating set of $G$, by $\gamma(G)$. For any integer $k\ge 1$, a function $f : V (G) \rightarrow \{0, 1, . . ., k\}$ is called a \emph{$\{k\}$-dominating function} if the sum of its function values over any closed neighborhood is at least $k$. The weight of a $\{k\}$-dominating function is the sum of its values over all the vertices. The $\{k\}$-domination number of $G$, $\gamma_{\{k\}}(G)$, is defined to be the minimum weight taken over all $\{k\}$-domination functions. <br>Bre\v{s}ar, Henning, and Klav\v{z}ar (On integer domination in graphs and Vizing-like problems. \textit{Taiwanese J. Math.} \textbf{10(5)} (2006) pp. 1317--1328) asked whether there exists an integer $k\ge 2$ so that $\gamma_{\{k\}}(G\cart H)\ge \gamma(G)\gamma(H)$.<br>In this note we use the Roman $\{2\}$-domination number, $\gamma_{R2}$ of Chellali, Haynes, Hedetniemi, and McRae, (Roman $\{2\}$-domination. \textit{Discrete Applied Mathematics} \textbf{204} (2016) pp. 22-28.) to prove that if $G$ is a claw-free graph and $H$ is an arbitrary graph, then $\gamma_{\{2\}}(G\cart H)\ge \gamma_{R2}(G\cart H)\ge \gamma(G)\gamma(H)$, which also implies the conjecture for all $k\ge 2$.