\documentclass[12pt]{article}
\usepackage{amssymb, amsmath, amsthm, latexsym, e-jc}
\specs{P8}{19}{2012}

\def\g{\gamma}
\def\cd{\centerdot}

\theoremstyle{definition}
\newtheorem{Thm}{Theorem}
\newtheorem{case}{Case}


\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\rqed}{\renewcommand{\qed}{}}

\date{\dateline{Apr 7, 2010}{Dec 21, 2011}{Jan 6, 2012}\\
\small Mathematics Subject Classification: 05C69}

\begin{document}

\title{An improved inequality related to Vizing's conjecture}

\author{Stephen Suen and Jennifer Tarr\\
\small University of South Florida\\
\small \texttt{ssuen@usf.edu, jtarr2@mail.usf.edu}}

\maketitle

\begin{abstract}
Vizing conjectured in 1963 that $\gamma(G \Box H) \geq \gamma(G)\gamma(H)$ for any graphs $G$ and $H$. A graph $G$ is said to satisfy Vizing's conjecture if the conjectured inequality holds for $G$ and any graph $H$.  Vizing's conjecture has been proved for $\gamma(G) \le 3$, and it is known to hold for other classes of graphs. Clark and Suen in 2000 showed that $\gamma(G \Box H) \geq \frac{1}{2}\gamma(G)\gamma(H)$ for any graphs $G$ and $H$.   We give a slight improvement of this inequality by tightening their arguments. 
\end{abstract}

\begin{center}
{\small
\textbf{Keywords}. Graph domination, Cartesian product, Vizing's conjecture
}
\end{center}

We use $V(G), E(G), \g(G)$, respectively, to denote the vertex set, edge set and domination number of the (simple) graph $G$.  A $\g$-set of a graph $G$ is a dominating set of $G$ with minimum cardinality.  For graphs $G$ and $H$, the Cartesian product $G \Box H$ is the graph with vertex set $V(G) \times V(H)$ and two vertices are adjacent if and only if they are equal in one coordinate and adjacent in the other. In 1963, V.~G.~Vizing \cite{Vizing63} conjectured that for any graphs $G$ and $H$, 
\[
\g(G \Box H) \ge \g(G)\g(H).
\]
The reader is referred to Hartnell and Rall \cite{Hartnell98} and Bre\v{s}ar et al.~\cite{Bresar99} for a summary of the history and recent progress on Vizing's conjecture.  Clark and Suen \cite{Clark00} in 2000 showed that for any graphs $G$ and $H$,
\[
\gamma(G \Box H) \ge \frac{1}{2}\gamma(G)\gamma(H).
\]
The following theorem is a slight improvement of this inequality. 

\begin{Thm} For any graphs $G$ and $H$, $\gamma(G \Box H) \geq \frac{1}{2}\gamma(G)\gamma(H) + \frac{1}{2}\min\{\gamma(G),\gamma(H)\}$.
\end{Thm}
\begin{proof}
Let $G$ and $H$ be arbitrary graphs, and let $D$ be a $\gamma$-set of the Cartesian product $G \Box H$. Let $\{u_1, u_2, \dots,u_{\gamma(G)}\}$ be a $\gamma$-set of $G$.  We partition $V(G)$ into $\gamma(G)$ sets $\Pi_{1\centerdot}, \Pi_{2\centerdot}, \dots, \Pi_{\gamma(G)\centerdot}$, where $u_i \in \Pi_{i\centerdot}$ for all $i = 1, 2, \dots, \gamma(G)$ and if $u \in \Pi_{i\centerdot}$ then $u = u_i$ or $\{u, u_i\} \in E(G)$. 

Let $P_{i\centerdot}$ denote the projection of $(\Pi_{i\centerdot} \times V(H)) \cap D$ onto $H$.  That is, 
\[
P_{i\cd} = \{v \in V(H) \mid (u,v) \in D \text{ for some $u\in\Pi_{i\cd}$}\}.
\]
Define $C_{i\cd}= V(H) - N_H[P_{i\cd}]$ as the complement of $N_H[P_{i\cd}]$, where $N_H[X]$ is the set of closed neighbors of $X$ in graph $H$.  As $P_{i\cd} \cup C_{i\cd}$ is a dominating set of $H$, we have
\begin{equation}
\label{C}
\abs{P_{i\cd}} + \abs{C_{i\cd}} \ge \g(H), \qquad i = 1, 2, \ldots, \g(G).
\end{equation}
For $v\in V(H)$, let 
\[
D_{\centerdot v} = \{u \mid (u,v) \in D\} \quad \text{and} \quad S_{\centerdot v} = \{i \mid v \in C_{i\cd}\}.
\]
Observe that if $i \in S_{\centerdot v}$ then the vertices in $\Pi_{i\centerdot} \times \{v\}$ are dominated ``horizontally'' by vertices in $D_{\cd v} \times \{v\}$.  Let $S_H$ be the number of pairs $(i,v)$ where $i=1,2,\ldots,\g(G)$ and $v\in C_{i\cd}$.  Then obviously
\[
S_H = \sum_{v \in V(H)} \abs{ S_{\centerdot v}} = \sum_{i = 1}^{\gamma(G)} \abs{C_{i\centerdot} }.
\]
Since $D_{\centerdot v} \cup \{u_i \mid i \notin S_{\centerdot v}\}$ is a dominating set of $G$, we have
\[
\abs{D_{\centerdot v}} + (\gamma(G) - \abs{S_{\centerdot v}}) \geq \gamma(G),
\]
giving that
\begin{equation}
\label{SV}
\abs{S_{\centerdot v}} \leq \abs{D_{\centerdot v}}.
\end{equation} 
Summing over $v \in V(H)$, we have
\begin{equation} 
\label{SH1}
S_H \leq \abs{D}.
\end{equation}

We now consider two cases based on \eqref{C}.

\begin{case} Assume $\abs{P_{i\centerdot}} + \abs{C_{i\centerdot}} > \gamma(H)$ for all $i = 1, \dots,\gamma(G)$. Then as $\abs{(\Pi_{i\centerdot} \times V(H))\cap D}\ge \abs{P_{i\cd}}$, we have
\[
\sum_{i = 1}^{\gamma(G)} (\abs{C_{i\centerdot}} + \abs{(\Pi_{i\centerdot} \times V(H)) \cap D}) \geq \sum_{i = 1}^{\gamma(G)} (\gamma(H) + 1),
\]
which implies that
\begin{equation} 
\label{SH2}
S_H + \vert D \vert \geq \gamma(G)\gamma(H) + \gamma(G).
\end{equation} 
Combining \eqref{SH1} and \eqref{SH2} gives that
\begin{equation} 
\label{ineq1}
\gamma(G \Box H) = \abs{D} \geq \frac{1}{2}\gamma(G)\gamma(H)+ \frac{1}{2}\gamma(G).
\end{equation}
\end{case}

\begin{case} Assume $\vert P_{i\centerdot} \vert + \vert C_{i\centerdot} \vert = \gamma(H)$ for some $i = 1, \dots, \gamma(G)$. Note that $P_{i\centerdot} \cup C_{i\centerdot}$ is a $\gamma$-set of $H$.  We now use this $\g$-set of $H$ to partition $V(H)$ in the same way as $V(G)$ is partitioned above.  That is, label the vertices in $P_{i\centerdot} \cup C_{i\centerdot}$ as $v_1, v_2,\dots,v_{\gamma(H)}$, and let $\{\Pi_{\centerdot j} \mid 1 \leq j \leq \gamma(H)\}$  be a partition of $H$ such that for all $j = 1, \dots, \gamma(H)$, $v_j \in \Pi_{\centerdot j}$ and if $v \in \Pi_{\centerdot j}$, either $v = v_j$ or $\{v, v_j\} \in E(H)$.   We next define the sets $P_{\cd j}, C_{\cd j}, S_{u\cd}$ and $D_{u\cd}$ in the same way $P_{i\cd}, C_{i\cd}, S_{\cd v}$ and $D_{\cd v}$ are defined above.  To be specific, for $1 \le j \le \g(H)$, let
\[
P_{\cd j} = \{u \in V(G) \mid (u,v) \in D \text{ for some $v\in\Pi_{\cd j}$}\}, \quad \text{and} \quad C_{\cd j} = V(G)-N_G[P_{\cd j}],
\]
and for $u\in V(G)$, let
\[
D_{u\cd} = \{v \mid (u,v) \in D\} \quad \text{and} \quad S_{u\cd} = \{j \mid u \in C_{\cd j}\}.
\]
Similarly, we have 
\[
S_G = \sum_{u \in V(G)} \abs{S_{u\centerdot}} = \sum_{j=1}^{\gamma(H)} C_{\centerdot j}.
\]

For $u \in V(G)$, let $\hat{D}_{u\cd} = \{v_j \mid (u,v_j) \in D_{u\centerdot}, 1 \le j \le \g(H)\}$.  We claim that
\begin{equation}
\label{SU}
\abs{S_{u\centerdot}} \leq \abs{D_{u\centerdot}} - \abs{\hat{D}_{u\cd}}.
\end{equation}
This is because $D_{u\centerdot} \cup \{v_j \mid j \notin S_{u\centerdot}\}$ is a dominating set of $H$, with  
\[
D_{u\centerdot} \cap \{v_j \mid j \notin S_{u\centerdot}\} = \hat{D}_{u\cd},
\]
and the argument for proving \eqref{SU} follows in the same way as \eqref{SV} is proved.  To make use of the claim, we note that when we partition the vertices of $H$, we have at least $\gamma(H)$ vertices in $D$ that are of the form $(u,v_k)$.  Indeed, for each $k=1,2,\ldots, \g(H)$, either $v_k \in P_{i\centerdot}$, which implies $(u,v_k) \in D$ for some $u \in \Pi_{i\cd}$, or $v_k \in C_{i\centerdot}$, which implies that the vertices in $\Pi_{i\cd}\times\{v_k\}$ are dominated ``horizontally'' by some vertices $(u',v_k)\in D$.  It therefore follows that
\[
\sum_{u \in V(G)}  \abs{\hat{D}_{u\cd}} \ge \g(H),
\]
and hence summming both sides of \eqref{SU}
\[
\sum_{u \in V(G)} \abs{S_{u\centerdot}} \leq \sum_{u \in V(G)} (\abs{D_{u\centerdot}} - \abs{\hat{D}_{u\cd}})
\]
gives that
\begin{equation} 
\label{SG1}
S_G \leq \vert D \vert - \gamma(H).
\end{equation}

To complete the proof, we note that similar to \eqref{C}, we have
\[
\abs{P_{\cd j}} + \abs{C_{\cd j}} \ge \g(G), \qquad j = 1, 2, \ldots, \g(H),
\]
and summing over $j$ gives that
\begin{equation} 
\label{SG2}
\vert D \vert + S_G \geq \gamma(G)\gamma(H).
\end{equation}
Combining \eqref{SG1} and \eqref{SG2}, we obtain
\begin{equation}
\label{ineq2} 
\gamma(G \Box H) \geq \frac{1}{2}\gamma(G)\gamma(H) + \frac{1}{2}\gamma(H). 
\end{equation} 
\end{case}
As either \eqref{ineq1} or \eqref{ineq2} holds, it follows that
\[
\gamma(G \Box H) \geq \frac{1}{2}\gamma(G)\gamma(H)+ \frac{1}{2}\min\{\gamma(G),\gamma(H)\}.\qed
\]
\rqed
\end{proof}

\begin{thebibliography}{99} 

\bibitem{Bresar99} B. Bre\v{s}ar, P. Dorbex, W. Goddard, B. L. Hartnell, M. A. Henning, S. Klav\v{z}ar, and D. F. Rall, Vizing's Conjecture: A Survey and Recent Results,  \emph{Journal of Graph Theory}, 69, 46–-76, 2012.

\bibitem{Clark00} W. E. Clark and S. Suen, An Inequality Related to Vizing's Conjecture,  \emph{The Electron. J. of Combin.} 7, Note 4, 2000.

\bibitem{Hartnell98} B. Hartnell and D. F. Rall, Domination in Cartesian Products: Vizing's 
Conjecture, in \emph{Domination in Graphs---Advanced Topics}, edited by Haynes et al., 163--189,
Marcel Dekker, Inc, New York, 1998. 

\bibitem{Vizing63} V. G. Vizing, The Cartesian product of graphs, \emph{Vy\v{c}isl. Sistemy} 9, 30-43, 1963.

\end{thebibliography}

\end{document}