% standard formatting for electronic journal of combinatorics
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P25}{20(3)}{2013}
\sloppy
\usepackage{tikz, tikz-3dplot}
\usepackage{amssymb}
\usepackage{amsmath, amsthm, enumitem}
\usepackage{graphicx}
\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem*{cor_nonum}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{prop}{Proposition}
\newtheorem{example}{Example}
\newtheorem{fact}{Fact}
\newtheorem{defi}{Definition}
%\theoremstyle{def}
%\newtheorem{def}{Definition}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\bf A Note on Total and Paired Domination\\ of Cartesian Product Graphs}

\author{K. Choudhary\\
\small Department of Mathematics and Statistics\\[-0.8ex]
\small Indian Institute of Technology Kanpur\\[-0.8ex]
\small Kanpur, India\\
\small \texttt{keerti.india@gmail.com}\\
\and
S. Margulies\\
\small Department of Mathematics\\[-0.8ex]
\small Pennsylvania State University\\[-0.8ex]
\small State College, PA, U.S.A. \\
\small \texttt{margulies@math.psu.edu}\\
\and
I. V. Hicks\\
\small Department of Computational and Applied Mathematics\\[-0.8ex]
\small Rice University\\[-0.8ex]
\small Houston, TX, U.S.A. \\
\small \texttt{ivhicks@rice.edu}
}

\date{\dateline{Sep 9, 2011}{Jul 27, 2013}{Aug 23, 2013}\\
\small Mathematics Subject Classifications: 05C69}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\maketitle

\begin{abstract}
A dominating set $D$ for a graph $G$ is a subset of $V(G)$ such that any
vertex not in $D$ has at least one neighbor in $D$.
The domination number $\gamma(G)$ is the size of a minimum dominating set in $G$. Vizing's conjecture from 1968 states that for the Cartesian product of graphs $G$ and $H$, $\gamma(G) \gamma(H) \leq \gamma(G \Box H)$, and Clark and Suen (2000) proved that $\gamma(G) \gamma(H) \leq 2\gamma(G \Box H)$. In this paper, we modify the approach of Clark and Suen to prove similar bounds for total and paired domination in the general case of the $n$-Cartesian product graph $A_1 \Box \cdots \Box A_n$. As a by-product of these results, improvements to known total and paired domination inequalities follow as natural corollaries for the standard $G \Box H$. 
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
We consider simple undirected graphs $G=(V,E)$ with vertex set $V$ and edge set $E$.
The open neighborhood of a vertex $v\in V(G)$ is denoted by $N_{G}(v)$,
and closed neighborhood by $N_{G}[v]$.
A dominating set $D$ of a graph $G$ is a subset of $V(G)$ such that for all $v$,
$N_{G}[v] \cap D \neq \emptyset$.
A $\gamma$-set of $G$ is a minimum dominating set for $G$, and its size is denoted
$\gamma(G)$.
A \emph{total} dominating set $D$ of a graph $G$ is a subset of $V(G)$ such that for all $v$,
$N_{G}(v) \cap D \neq \emptyset$.
A $\gamma _{t}$-set of $G$ is a minimum total dominating set for $G$, and its size
is denoted $\gamma _{t}(G)$.
A \emph{paired} dominating set $D$ for a graph $G$ is a dominating set such that the subgraph of $G$ induced by $D$ (denoted $G[D]$) has a perfect matching.
A $\gamma_{pr}$-set of $G$ is a minimum paired dominating set for $G$,
and its size is denoted $\gamma_{pr}(G)$.
In general, for a graph containing no isolated vertices,
$\gamma(G) \leq \gamma_{t}(G) \leq \gamma_{pr}(G)$. 
%For an easy example, consider %$P_5$, the path on five vertices, with vertices consecutively indexed from $1$ to %$5$. Then, a minimum dominating set consists of vertices $\{2,4\}$, a minimum 
%total dominating set consists of vertices $\{2,3,4\}$ and a minimum paired 
%dominating set consists of vertices $\{1,2,3,4\}$.

The Cartesian product graph, denoted $G \Box H$, is the graph with
vertex set $V(G)\times V(H)$, where vertices $gh$ and $g'h'$ are adjacent
whenever $g = g'$ and $(h,h')\in E(H)$, or $h = h'$ and $(g,g') \in E(G)$.
Just as the Cartesian product of graphs $G$ and $H$ is denoted $G \Box H$, the $n$-product of graphs $A_{1} , A_{2} ,\ldots, A_{n}$ is denoted as $A_{1} \Box A_{2} \Box \cdots \Box A_{n}$, and has vertex set
$V(A_{1})\times V(A_{2})\times \cdots \times V(A_{n})$, where vertices
$u_{1}\cdots u_{n}$ and $v_{1}\cdots v_{n}$ are adjacent if and only if
for some $i$, $(u_{i}, v_{i})\in E(A_{i})$, and $u_{j} = v_{j}$ for
all other indices $j \neq i$.

Vizing's conjecture from 1968 states that $\gamma(G) \gamma(H) \leq \gamma(G \Box H)$. For a thorough review of the activity on this famous open problem, see \cite{viz_survey_2009} and references therein. In 2000, Clark and Suen \cite{viz_clark_suen} proved that 
$\gamma(G) \gamma(H) \leq 2\gamma(G \Box H)$ by a sophisticated double-counting argument which involved projecting a $\gamma$-set of the product graph $G\Box H$ down onto the graph $H$. In this paper, we slightly modify the Clark and Suen double-counting approach and instead project subsets of $G \Box H$ down onto both graphs $G$ and $H$, which allows us to prove several theorems/corollaries relating to total and paired domination. In this section, we state the results, and in Section \ref{sec_results}, we prove the results.

\begin{thm}~\label{thm_max_t}
Given graphs $A_{1} , A_{2} ,\ldots, A_{n}$ containing no isolated vertices,
\begin{align*}
\displaystyle \gamma(A_1) \prod\limits _{i=2}^{n} \gamma_{t}(A_{i}) \leq n\gamma(A_{1} \Box A_{2} \Box \cdots \Box A_{n})~.
\end{align*}
\end{thm}

In 2008, Ho \cite{ho_total_dom} proved  $\gamma_{t}(G) \gamma _{t}(H) \leq 2\gamma_{t}(G \Box H)$, an inequality for total domination precisely analogous to the Clark and Suen inequality for domination. In this paper, we extend this result to the $n$-product case, and then Ho's inequality becomes a special case of a more general result.
%domination analogous to the Clark and Suen inequality for domination. In particular, Ho proved $\gamma_{t}(G) \gamma _{t}(H) \leq 2\gamma_{t}(G \Box H)$
%In 2008, Ho \cite{ho_total_dom} proved an inequality for total
%domination analogous to the Clark and Suen inequality for domination. In particular, Ho proved $\gamma_{t}(G) \gamma _{t}(H) \leq 2\gamma_{t}(G \Box H)$. We extend this result to the $n$-product case, and then Ho's result follows as a corollary:
\begin{thm}~\label{thm_t_n}
Given graphs $A_{1} , A_{2} ,\ldots, A_{n}$ containing no isolated vertices,
\begin{align*}
\displaystyle \prod\limits _{i=1}^{n} \gamma_{t}(A_{i}) \leq n\gamma_{t}(A_{1} \Box A_{2} \Box \cdots \Box A_{n})~.
\end{align*}
\end{thm}
In 2007, Bre\u{s}ar, Henning and Rall \cite{rall_pr} proved that  $\gamma_{pr}(G) \gamma _{pr}(H) \leq 8\gamma_{pr}(G \Box H)$, and in 2010, Hou and Jiang \cite{hou_jiang_pr_dom} proved that $\gamma_{pr}(G) \gamma _{pr}(H) \leq 7\gamma_{pr}(G \Box H)$. We extend these results to the $n$-product case, and attain an improvement to these inequalities as a corollary:
\begin{thm}~\label{thm_pr_n}
Given graphs $A_{1},\ldots, A_{n}$ containing no isolated vertices,
\begin{align*}
\displaystyle\prod\limits_{i=1}^{n} \gamma _{pr}(A_i) \leq 2^{n-1}(2n - 1)\gamma _{pr}(A_1 \Box \cdots \Box A_n)~.
\end{align*}
\end{thm}
\begin{cor_nonum}
Given graphs $G$ and $H$ containing no isolated vertices,
\begin{align*}
\gamma_{pr}(G) \gamma _{pr}(H) \leq 6 \gamma_{pr }(G \Box H)~.
\end{align*}
\end{cor_nonum}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Main Results} \label{sec_results}
We begin by introducing some notation which will be utilized throughout the proofs in this section. Given $S \subseteq V(A_1\Box \cdots \Box A_n)$, the projection of $S$ onto graph $A_i$ is defined as
\begin{align*}
\varPhi_{A_i}(S) &= \{a \in V(A_i) ~\rvert~\exists ~u_1\cdots u_n \in S \text{ with } a = u_i\}~.
\end{align*}
We partition the set of edges $E(A_1\Box \cdots \Box A_n)$ into $n$ sets. Thus, we define $E_i$ to be
\begin{align*}
E_i &= \Big\{\big(u_{1}\cdots u_{n}, v_{1}\cdots v_{n}\big) ~\lvert~ (u_{i}, v_{i})\in E(A_{i}) \text{, and $u_{j} = v_{j}$, for all other indices $j\neq i$}\Big\}~.
\end{align*}
An edge $e \in E_i$ is said to be an $E_i$-edge. For $u \in V(A_1\Box \cdots \Box A_n)$, the $i$-neighborhood of $u$ is defined as follows:
\begin{align*}
N_{\Box A_i}(u) &= \Big\{ v\in  V(A_1\Box \cdots \Box A_n) ~\lvert~\text{$v$ and $u$ are connected by $E_{i}$-edge} \Big\}~.
\end{align*}
Finally, we present a proposition utilized throughout our proofs. Although the more general $n$-dimensional case stated in Prop. \ref{fact2} is the proposition referenced within the proofs, we begin by separately stating the 2-dimensional case to clarify the overall idea.
\begin{prop}\label{fact1}
Let $M$ be a matrix containing only 0/1 entries. Then at least one of the following two statements are true:
%\begin{enumerate}[label=(\roman*)]
\begin{enumerate}[label=(\alph*)]
\item each column contains a 1,
\item each row contains a 0~.
\end{enumerate}
\end{prop}
Prop. \ref{fact1} refers only to binary matrices, or matrices containing only 0/1 entries. Prop. \ref{fact2} refers to \emph{$n$-ary} matrices, or (in this case) matrices containing only entries in $\{1,\ldots, n\}$. Furthermore, Prop.  \ref{fact1} refers only to two-dimensional matrices, or $d_1 \times d_2$ matrices $M$. Prop. \ref{fact2} refers to $n$-dimensional matrices, or $d_1 \times d_2 \times \cdots \times d_n$ matrices $M$. 
\begin{defi} \label{def_j_matrix} Let $M$ be a $d_1 \times d_2 \times \cdots \times d_n$, $n$-ary matrix. Then $M$ is a \underline{\emph{$j$-matrix}} if there exists a $j \in \{1,\ldots, n\}$ (not necessarily unique),
such that \textbf{each} of the $d_1 \times \cdots \times d_{j-1} \times 1 \times d_{j+1} \times \cdots \times d_n$ submatrices of $M$ contains an entry with value $j$.
\end{defi}

\begin{prop}\label{fact2}
Every $d_1 \times d_2 \times \cdots \times d_n$, $n$-ary matrix $M$ is a $j$-matrix for some $j \in \{1,\ldots,n\}$ (not necessarily unique).
\end{prop}

Note that, given any $d_1 \times d_2 \times \cdots \times d_n$ matrix, there are $d_j$ submatrices of the form $d_1 \times \cdots \times d_{j-1} \times 1 \times d_{j+1} \times \cdots \times d_n$. Following standard \textsc{Matlab} notation, we will denote such a submatrix as $M[:,\ldots,:, i_j , : ,\ldots, : ]$ with $1 \leq i_j \leq d_j$.

\begin{example}  \label{ex_jm} Here we see a  $4 \times 3 \times 3$,  3-ary (the entries are contained in the set $\{1,2,3\}$) matrix $M$. Using the notation specified above, $M[2, :, :]$ is denoted by the gray shaded region and $M[:, 1, :]$ is denoted by yellow shaded region. $M$ is both $1$-matrix and $2$-matrix, but not a $3$-matrix.

\begin{center}
\begin{tikzpicture}
		[c1/.style={very thick, gray},
			c2/.style={thick,gray},
			c4/.style={very thin, blue},
			c3/.style={->,blue,thick}]

% style of faces
\tikzset{facestyle/.style={fill=lightgray,draw=gray,very thin,line join=round}}

	\draw[c3] (0,0,0) -- (5.2,0,0) node[anchor=west]{$1$};
	\draw[c3] (0,0,0) -- (0,4,0) node[anchor=west]{$2$};
	\draw[c3] (0,0,0) -- (0,0,6.2) node[anchor=west]{$3$};

	\begin{scope}[canvas is xy plane at z=0]
		\path[facestyle, fill=white] (4,3) rectangle (0,0);
		\draw[c2] (0,0) grid (4,3);
		\path[facestyle, fill=lightgray, opacity=0.4] (2,3) rectangle (1,0);
		\path[facestyle, fill=yellow, opacity=0.3] (0,0) rectangle (4,1);
		\node at (0.5,2.5) {3};
		\node at (1.5,2.5) {1};
		\node at (2.5,2.5) {1};
		\node at (3.5,2.5) {3};
		\node at (3.5,1.5) {3};
		\node at (3.5,0.5) {2};
	\end{scope}

	\begin{scope}[canvas is xy plane at z=2]
		\path[facestyle, fill=white] (4,3) rectangle (0,0);
		\draw[c2] (0,0) grid (4,3);
		\path[facestyle, fill=lightgray, opacity=0.4] (2,3) rectangle (1,0);
		\path[facestyle, fill=yellow, opacity=0.3] (0,0) rectangle (4,1);
		\node at (0.5,2.5) {1};
		\node at (1.5,2.5) {2};
		\node at (2.5,2.5) {1};
		\node at (3.5,2.5) {3};
		\node at (3.5,1.5) {1};
		\node at (3.5,0.5) {3};
	\end{scope}

	\begin{scope}[canvas is xy plane at z=4]
		\path[facestyle, fill=white] (4,3) rectangle (0,0);
		\draw[c2] (0,0) grid (4,3);
		\path[facestyle, fill=lightgray, opacity=0.4] (2,3) rectangle (1,0);
		\path[facestyle, fill=yellow, opacity=0.3] (0,0) rectangle (4,1);
		\node at (0.5,2.5) {2};
		\node at (1.5,2.5) {1};
		\node at (2.5,2.5) {2};
		\node at (3.5,2.5) {2};
		\node at (0.5,1.5) {2};
		\node at (1.5,1.5) {1};
		\node at (2.5,1.5) {2};
		\node at (3.5,1.5) {2};
		\node at (0.5,0.5) {1};
		\node at (1.5,0.5) {2};
		\node at (2.5,0.5) {2};
		\node at (3.5,0.5) {1};
	\end{scope}

%\draw[xshift=6.5cm, yshift=1cm] node [right,text width=4.5cm,style=information text]
%    {
%      Example : In the figure M is $4 \times 3 \times 3$ ternary matrix.
%      $M[2_1, :]$ is denoted by gray shaded region, and
%      $M[:, 1_2, :]$ is denoted by yellow shaded region.
%      $M$ is both $1$-matrix and $2$-matrix, but not a $3$-matrix.
%    };

\end{tikzpicture}
\end{center}
\end{example}

\begin{proof}
For a pigeon-hole principle style proof, let $M$ be a $d_1 \times d_2 \times \cdots \times d_n$ $n$-ary matrix which is \textbf{not} a $j$-matrix for $1 \leq j \leq n-1 $. We will show that $M$ is an $n$-matrix.

Consider $j = 1$. Since $M$ is not a 1-matrix,
there exists at least one $1 \times d_2 \times d_3 \times \cdots \times d_n$
submatrix that does \emph{not} contain a 1. Without loss of generality, let
 $M[i_1,:,\ldots,:]$ with $1 \leq i_1 \leq d_1$ be such a matrix.
Next, consider $j = 2$. Since $M$ is also not a 2-matrix, let 
$M[:,i_2,:, \ldots,:]$ with $1 \leq i_2 \leq d_2$ be a $d_1 \times 1 \times d_3 \times \cdots \times d_n$ submatrix that does \emph{not} contain a 2.
Therefore, $M[i_1,i_2,:,\ldots,:]$
is a $1 \times 1 \times d_3 \times \cdots \times d_n$
submatrix that contains neither a 1 nor a 2.
We continue this pattern for $1 \leq j \leq n - 1$.
Since $M$ is \emph{not} a $j$-matrix for $1 \leq j \leq n-1$, let
$M[i_1,\ldots,i_{n-1},:]$ be the $1 \times 1\cdots 1 \times d_n$ submatrix containing no elements in the set $\{1,\cdots, n-1\}$. 
Therefore, for all $1 \leq i \leq d_n$, $M[i_1, \ldots, i_{n-1}, i] = n$, \emph{all} of the $d_1 \times \cdots \times d_{n-1} \times 1$ submatrices of $M$ contain an entry with value $n$. Thus, $M$ is an $n$-matrix.
\end{proof}

We now present the proofs of Theorems 1 through 3.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Proof of Theorem~\ref{thm_max_t}}
\begin{proof}

Let ${\{u^{1} _{1} ,\ldots, u^{1} _{\gamma(A_{1})}\} }$ be a $\gamma$-set of $A_1$. Partition $V(A_1)$ into sets $D^{1} _{1} ,\ldots, D^{1} _{\gamma(A_{1})}$
such that $u^{1}_{j} \in D^{1} _{j} \subseteq N_{A_1}[u^{1} _{j}]$ for $1 \leq j \leq \gamma(A_{1})$. Having partitioned $V(A_1)$ based on a minimum dominating set, we will now partition each of $V(A_2),\ldots,V(A_n)$ based on a minimum \emph{total} dominating set. For $i=2,\ldots,n$, let
${\{u^{i} _{1} ,\ldots, u^{i} _{\gamma_{t}(A_{i})}\} }$ be a $\gamma _{t}$-set of $A_{i}$, and $D^{i} _{1} ,\ldots, D^{i} _{\gamma_{t}(A_{i})}$ be the corresponding
partitions of $V(A_i)$ such that $D^{i} _{j} \subseteq N_{A_i}(u^{i} _{j})$. Note that this implies $u^i_j \notin D^{i} _{j}$.

Now let $Q = \{D^{1} _{1} ,\ldots, D^{1} _{\gamma (A_{1})}\} \times  \{D^{2} _{1} ,\ldots, D^{2} _{\gamma_t (A_{2})}\} \times\cdots \times \{D^{n} _{1} ,\ldots, D^{n} _{\gamma _{t}(A_{n})}\}$.
Then $Q$ forms a partition of $V(A_{1} \Box \cdots \Box A_{n})$ with $|Q| = \displaystyle \gamma(A_1) \prod\limits_{i=2}^{n} \gamma_{t}(A_{i})$. 

Let $D$ be a $\gamma$-set of $A_{1} \Box \cdots \Box A_{n}$. Then, for each $u\in V(A_{1} \Box \cdots \Box A_{n})$ not in $D$, there exists an $i$ such that $N _{\Box A_i}(u) \cap D$ is non-empty. Based on this observation, we define an $n$-ary $|V(A_1)| \times \cdots \times |V(A_n)|$ matrix $F$ such that:

\[
 F(u_1,\dots,u_n) =
 \begin{cases}
 1 & \text{if } (u_1\cdots u_n) \in D~, \text{ else}\\
 i_{\min} & \text{where~} i_{\min} = \min \{i~\lvert~N _{\Box A_i}(u_1\cdots u_n) \cap D \neq \emptyset \}~.
 \end{cases}
\]	
Observe that $F(u_1,\dots,u_n) = 1$ has two meanings: either $(u_1\cdots u_n) \in D$ or $(u_1\cdots u_n)$ is dominated an an $A_1$-edge. 

For $j=1,\ldots,n$, let $d_{j} \subseteq Q$ be the set of the elements in $Q$ such that the corresponding submatrices of $F$ are $j$-matrices. By Prop.~\ref{fact2}, each element of $Q$ belongs to at least one $d_{j}$-set. Then, $\displaystyle\gamma(A_{1})\prod\limits_{i=2}^{n} \gamma_{t}(A_{i}) \leq \displaystyle\sum\limits_{j=1}^{n} | d_{j}|$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{claim}\label{clm_di_out}
$ |d_{1}| \leq |D|$.
\end{claim}
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{proof}
Similar to $Q$, let $B = \{D^{2} _{1}, \ldots, D^{2} _{\gamma _{t}(A_{2})}\} \times \cdots \times \{D^{n} _{1} ,\ldots, D^{n} _{\gamma _{t}(A_{n})}\}$.
For convenience, denote $B$ as $\{B_{1}, \ldots, B_{|B|}\}$, where $\rvert B\rvert = \displaystyle\prod\limits_{i=2}^{n} \gamma_{t}(A_{i})$.

For $p=1,\ldots,|B|$, let $Z_{p} = D \cap (A_{1} \times B_{p})$, and
\begin{align*}
S_{p} = \big\{ {D}^{1}_{x} ~\rvert~ &\text{the submatrix of $F$ determined by $D^{1}_{x} \times B_p$ is a $1$-matrix},\\
&\text{with $x \in \{1,\ldots,\gamma(A_{1})\}$}\big\}~.
\end{align*}
Note that if $D^1_x \times B_{p}$ is a $1$-matrix for some $x \in \{1,\ldots,\gamma(A_{1})\}$ and $p \in \{1,\ldots,|B|\}$, then for each $w \in D^1_x$, the submatrix of $F$ corresponding to $\{w\} \times B_p$ contains a 1. Therefore,
$\{w\} \times B_p$ contains a vertex in $D$ or a vertex that is dominated by an $A_1$-edge. In either case, $\{w\} \times B_p$ contains a vertex that is dominated by $Z_p$. Thus, the projection of $D^1_x \times B_{p}$ on $A_1$ (i.e. $D^1_x$) is dominated by the projection of $Z_p$ on $A_1$.

We now claim that for $p=1,\ldots,|B|$, $|S_{p}| \leq |Z_{p}|$.
Let $S _{p} = \{{D}^{1}_{i_{1}}, {D}^{1}_{i_{2}}, \ldots, {D}^{1}_{i_{t}}\}$
and let $\varPhi_{A_1}(Z_p)$ be the projection of $Z_{p}$ on $A_1$.
Then, $\varPhi_{A_1}(Z_p)$ dominates $\cup _{x=1}^{t}{D}^{1}_{i _{x}}$, and 
for $i\notin \{i _{1}, i _{2}, \ldots, i _{t} \}$, ${u}^{1} _{i}$ dominates ${D}^{1} _{i}$.
Thus,  $\varPhi_{A_1}(Z_p) \cup \big\{ {u}^{1} _{i} ~\rvert~ i\notin \{i _{1}, i _{2}, \ldots, i _{t} \} \big \}$ is a dominating set for $A_{1}$.
Now, $\big| \varPhi_{A_1}(Z_p) \cup \big\{ {u}^{1} _{i} ~\rvert~ i\notin \{i _{1}, i _{2}, \ldots, i _{t} \} \big \} \big| \geq \gamma(A_{1})$, and
$\big| \big\{ {u}^{1} _{i} ~\rvert~ i\notin \{i _{1}, i _{2}, \ldots, i _{t} \} \big \} \big| = \gamma(A_{1}) - t$. Thus, $| \varPhi_{A_1}(Z_p)| \geq t$.
Hence, $|S_p| = t \leq |\varPhi_{A_1}(Z_p)| \leq | Z _{p} |$.
Finally, we see that $| d_{1}| = \displaystyle\sum\limits_{p=1}^{|B|} |S_{p} | \leq \displaystyle\sum\limits_{p=1}^{|B|} |Z _{p} | = |D|$.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{claim}\label{claim2}
For $j=2,\ldots,n$, $ |d_{j}| \leq |D|$.
\end{claim}
%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{proof}
We prove here that $ |d_{n}| \leq |D|$, but a similar proof can be performed for any other $j \geq 2$.
Let $B = \{D^{1}_{1}, \ldots, D^{1}_{\gamma(A_{1})}\} \times \{D^{2} _{1}, \ldots, D^{2} _{\gamma _{t}(A_{2})}\} \times \cdots \times \{D^{n-1} _{1} ,\ldots, D^{n-1} _{\gamma _{t}(A_{n-1})}\}$.
For convenience, denote $B$ as $\{B_{1}, \ldots, B_{|B|}\}$, where $\rvert B\rvert = \displaystyle \gamma(A_{1}) \prod\limits_{i=2}^{(n-1)} \gamma_{t}(A_{i})$.

For $p=1,\ldots,|B|$, let $Z_{p} = D \cap (B_{p} \times A_{n})$, and
\begin{align*}
S_{p} = \big\{ {D}^{n}_{x} ~\rvert~ &\text{the submatrix of $F$ determined by $B_{p}\times {D}^{n}_{x}$ is an $n$-matrix},\\
&\text{with $x \in \{1,\ldots,\gamma_{t}(A_{n})\}$}\big\}~.
\end{align*}
Note that if $B_{p}\times D^n_x$ is a $n$-matrix for some $p \in \{1,\ldots,|B|\}$ and $x \in \{1,\ldots,\gamma_{t}(A_{n})\}$, then, for each $w\in D^n_x$, the submatrix of $F$ corresponding to $B_p \times \{w\}$ contains an $n$. Therefore, each $B_p \times \{w\}$ contains a vertex that is dominated by an $A_n$-edge. Therefore, each vertex in the projection of $B_{p}\times D^n_x$ on $A_n$ (i.e., each vertex $w \in D^n_x \subseteq V(A_n)$) is dominated by a vertex from $\varPhi_{A_n}(Z_p)$, \emph{other than itself}. In other words, the projection of $B_{p}\times D^n_x$ on $A_n$ (i.e. $D^n_x$) is \emph{non-self-dominated} by the projection of $Z_p$ on $A_n$.

We now claim that for $p=1,\ldots,|B|$, $|S_{p}| \leq |Z_{p}|$. Let $S _{p} = \{{D}^{n}_{i_{1}}, {D}^{n}_{i_{2}}, \ldots, {D}^{n}_{i_{t}}\}$ and
let $\varPhi_{A_n}(Z_p)$ be the projection of $Z_{p}$ on $A_n$. Then, $\cup _{x=1}^{t}{D}^{n}_{i _{x}}$ is \emph{non-self-dominated} by $\varPhi_{A_n}(Z_p)$, and $\varPhi_{A_n}(Z_p) \cup \big\{ {u}^{n} _{i} ~\rvert~ i\notin \{i _{1}, i _{2}, \ldots,i_{t} \} \big \}$ is a total dominating set of $A_{n}$.
Now, $\big|\varPhi_{A_n}(Z_p) \cup \big\{ {u}^{n} _{i} ~\rvert~ i\notin \{i _{1}, i _{2}, \ldots, i _{t}\} \big\}\big| \geq \gamma_{t}(A_{n})$,
and $\big| \big\{ {u}^{n} _{i} ~\rvert~ i\notin \{i _{1}, i _{2}, \ldots, i _{t}\} \big\}\big | = \gamma_{t}(A_{n}) - t$. Thus, $| \varPhi_{A_n}(Z_p)| \geq t$.
Hence, $|S_p| = t \leq |\varPhi_{A_n}(Z_p)| \leq | Z _{p} |$.
Finally, we see that $| d_{n}| = \displaystyle\sum\limits_{p=1}^{|B|} |S_{p} | \leq \displaystyle\sum\limits_{p=1}^{|B|} |Z _{p} | = |D|$.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%
To conclude the proof, we observe that
\begin{align*}
\displaystyle \gamma(A_{1}) \prod\limits_{i=2}^{n} \gamma_{t}(A_{i}) \leq
\displaystyle\sum\limits_{j=1}^{n} | d_{j}| \leq   n| D| =  n\gamma(A_{1} \Box \cdots \Box A_{n})~.
\end{align*}
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%
We conclude this section with the following corollary.
\begin{cor_nonum}
Given graphs $G$ and $H$ containing no isolated vertices,
\begin{align*}
\max\{\gamma(G) \gamma _{t}(H), \gamma _{t}(G) \gamma(H)\} \leq 2\gamma(G \Box H)~.
\end{align*}
\end{cor_nonum}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Proof of Theorem~\ref{thm_t_n}}
\begin{proof}
For $i=1,\ldots,n$, let ${\{u^{i} _{1} ,..., u^{i} _{\gamma_{t}(A_{i})}\} }$ be a $\gamma _{t}$-set of $A_{i}$, and
$D^{i} _{1} ,\ldots, D^{i} _{\gamma_{t}(A_{i})}$ be the corresponding partitions of $V(A_{i})$ such that $D^i _{j} \subseteq N_{A_{i}}(u^i _{j})$.

Let $Q = \{D^{1} _{1} ,\ldots, D^{1} _{\gamma _{t}(A_{1})}\} \times \cdots \times \{D^{n} _{1} ,\ldots, D^{n} _{\gamma _{t}(A_{n})}\}$.
Then $Q$ forms a partition of $V(A_{1} \Box \cdots \Box A_{n})$ with 
$|Q| = \displaystyle\prod\limits_{i=1}^{n} \gamma_{t}(A_{i})$. 

Let $D$ be a $\gamma_{t}$-set of $A_{1} \Box \cdots \Box A_{n}$. Then, for each $u\in V(A_{1} \Box \cdots \Box A_{n})$, there exists an $i$ such that $N _{\Box A_i}(u) \cap D$ is non-empty. Based on this observation we define an $n$-ary $|V(A_1)| \times \cdots \times |V(A_n)|$ matrix $F$ such that:
\begin{align*}
F(u_1,\dots,u_n) &= \min \{i~\lvert~N _{\Box A_i}(u_1\cdots u_n) \cap D \neq \emptyset \}~.
\end{align*}
For $j=1,\ldots,n$, let $d_{j} \subseteq Q$ be the set of the elements in $Q$ which are $j$-matrices. By Prop.~\ref{fact2}, each element of $Q$ belongs to at least one $d_{j}$-set. Then, $\displaystyle\prod\limits_{i=1}^{n} \gamma_{t}(A_{i}) \leq \displaystyle\sum\limits_{j=1}^{n} | d_{j}|$.

\begin{claim}\label{claim3}
For $j=1,\ldots,n$, $ |d_{j}| \leq |D|$.
\end{claim}

\begin{proof}
The proof is copy of proof of Claim \ref{claim2}, except that here
$B = \{D^{1} _{1}, \ldots, D^{1} _{\gamma _{t}(A_{1})}\} \times \cdots \times \{D^{n-1} _{1} ,\ldots, D^{n-1} _{\gamma _{t}(A_{n-1})}\}$,
and $\rvert B\rvert = \displaystyle\prod\limits_{i=1}^{(n-1)} \gamma_{t}(A_{i})$.
\end{proof}

Thus we have,
$\displaystyle\prod\limits_{i=1}^{n} \gamma_{t}(A_{i}) \leq \displaystyle\sum\limits_{j=1}^{n} | d_{j}| \leq   n| D| =  n\gamma_{t}(A_{1} \Box \cdots \Box A_{n})$.
\end{proof}

We conclude by observing that Ho's inequality follows as a corollary to Thm. \ref{thm_t_n}.
\begin{cor_nonum}[Ho~\cite{ho_total_dom}]
Given graphs $G$ and $H$ containing no isolated vertices,
\begin{align*}
\gamma_{t}(G) \gamma _{t}(H) \leq 2\gamma_{t}(G \Box H)~.
\end{align*}
\end{cor_nonum}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Proof of Theorem~\ref{thm_pr_n}}
\begin{proof}
For $i=1,\ldots,n$, let $k_i = \gamma_{pr}(A_{i})/2$, and $\{x^{i}_{1},y^i_1 ,\ldots, x^{i}_{k_i}, y^{i}_{k_i} \}$
be a $\gamma _{pr}$-set of $A_{i}$, where for each $A_i$ and $1 \leq j \leq k_i$,
$(x^i_{j}, y^i_{j}) \in E(A_i)$. Partition each $V(A_i)$ into sets $D^i _{1} ,\ldots, D^i _{k_i}$, such that
$\{x^i_{j}, y^i_{j} \} \subseteq D^i_{j} \subseteq N_{A_{i}}[x^i_{j}] \cup N_{A_{i}}[y^i_{j}]$
for $1 \leq j \leq k_i$. 

Let $Q = \{D^{1} _{1} ,\ldots, D^{1} _{k_1}\} \times \cdots \times \{D^{n} _{1} ,\ldots, D^{n} _{k_n}\}$.
Then $Q$ forms a partition of $V(A_{1} \Box \cdots \Box A_{n})$ with 
$|Q| = \displaystyle\prod\limits_{i=1}^{n} \gamma_{pr}(A_{i})/2 =  \frac{1}{2^n}\displaystyle\prod\limits_{i=1}^{n} \gamma_{pr}(A_{i})$. 

Let $D$ be a $\gamma_{pr}$-set of $A_{1} \Box \cdots \Box A_{n}$. Then, for each $u\in V(A_{1} \Box \cdots \Box A_{n})$, there exists an $i$ such that $N _{\Box A_i}(u) \cap D$ is non-empty. Based on this observation, we define $n$ different matrices $F^i$ with $i = 1,\ldots, n$, where each of the $n$ matrices is an $n$-ary $|V(A_1)| \times \cdots \times |V(A_n)|$ matrix $F^i$ such that:
\[
 F^i(u_1,\ldots,u_n) =
 \begin{cases}
 i & \text{if } u_1\cdots u_n \in D~, \text{ else}\\
j_{\min} & \text{where~} j_{\min} = \min \{~j~\lvert~N _{\Box A_j}(u_1\cdots u_n) \cap D \neq \emptyset \}~.
 \end{cases}
\]
Thus, each of the $n$ matrices $F^i$ with $i = 1,\ldots,n$ differs only in the entries that correspond to vertices in the paired dominating set $D$.

For $j=1,\ldots,n$ and $i = 1,\ldots,n$,  let $d^i_{j} \subseteq Q$ be
the set of the elements in $Q$ which are $j$-matrices in the matrix $F^i$.
By Prop.~\ref{fact2}, each element of $Q$ belongs to at least one $d^i_{j}$-set
for each $i = 1,\ldots,n$.
Now, if an element $q \in Q$ belongs to the $d^i_{j}$-set, then
$q$ also belongs to the $d^j_{j}$-set. To see this, if $M_i$ and $M_j$ are the submatrices determined by $q$ with respect to the matrices $F^i$ and $F^j$, respectively, then all the entries that do not
match in $M_i$ and $M_j$ have value $j$ in $M_j$.
Thus, each $q \in Q$ belongs to at least one $d^i_{i}$-set
for some $i \in \{1,\ldots,n\}$.
Then, $\displaystyle \frac{1}{2^n} \prod\limits_{i=1}^{n} \gamma_{pr}(A_{i}) \leq
\displaystyle\sum\limits_{i=1}^{n} | d^i_{i}|$.

Similar to $Q$, let $B = \{D^{1} _{1}, \ldots, D^{1} _{k_1}\} \times \cdots \times \{D^{n-1} _{1} ,\ldots, D^{n-1} _{k_{n-1}}\}$.
For convenience, we denote $B$ as $\{B_{1}, \ldots, B_{|B|}\}$, where $\rvert B\rvert = \displaystyle\prod\limits_{i=1}^{n-1} \gamma_{pr}(A_{i})/2 =\frac{1}{2^{n-1}}\displaystyle\prod\limits_{i=1}^{n-1} \gamma_{pr}(A_{i})$. Since $D$ is a $\gamma_{pr}$-set, the subgraph of $A_{1} \Box \cdots \Box A_{n}$ induced by $D$ has a perfect matching. Let
\begin{align*}
D_{i} &= \{u \in D ~\rvert~ \text{the matching edge incident to $u$ is in $E_i$}\}~.
\end{align*}
Then, $D$ can be written as the disjoint union of the subsets $D_i$. For $p=1,\ldots,|B|$ and $i = 1,\ldots,n$, let $Z^i_{p} = D_i \cap (B_{p} \times A_{n})$, and
\begin{align*}
%S^i_{p} &= \big\{ {D}^{n}_{x} ~\rvert~ \text{the submatrix of $F^n$ determined by $B_{p}\times {D}^{n}_{x}$ is an $i$-matrix, with $x \in \{1,\ldots,k_n\}$}\big\}~.
S_{p} = \big\{ {D}^{n}_{x} ~\rvert~ &\text{the submatrix of $F^n$ determined by $B_{p}\times {D}^{n}_{x}$ is an $n$-matrix},\\
&\text{with $x \in \{1,\ldots,k_n\}$}\big\}~.
\end{align*}

Then, $|d^n_{n}| = \displaystyle\sum\limits_{p=1}^{|B|} |S_{p} |~. $

\begin{claim}\label{claim_n_pr_dj_d}
For $p=1,\ldots,|B|$, 
$2|S_p| \leq 2\lvert Z^1_p\lvert + \cdots + 2\lvert Z^{n-1}_p\lvert + |Z^n_{p}|$. 
\end{claim}
\begin{proof}Let
$S_{p} = \{{D}^{n}_{j_{1}}, {D}^{n}_{j_{2}}, \ldots, {D}^{n}_{j_{t}}\}$, and for $j = 1,\ldots, n$, let $V_j = \varPhi_{A_n}(Z^j_{p})$. Note that $|V_j| \leq |Z^j_{p}|$. Additionally, let $C = \big\{ x^n_{j} ~\rvert~ j\notin \{j _{1}, j _{2},\ldots, j _{t}\}\big\}
\cup \big\{ y^n_{j} ~\rvert~ j\notin \{j _{1}, j _{2}, \ldots, j _{t}\}\big\}$.

Let $M$ be the matching on $V_n \cup C$ formed by taking all of the $\{x^n_{j}, y^n_{j}\}$ edges induced by the vertices in $C$, and then adding the edges from a maximal matching on the remaining unmatched vertices in $V_n$. Then, $E = V_1 \cup \cdots \cup V_n \cup C$ is a dominating set of $A_n$ with $M$ as a matching. Let $M_1 = V(M)$ and
$M_2 = (V_n \cup C)\backslash M_1$. We note that $M_1$ consists of all the vertices in $C$ plus the matched vertices from $V_n$, and $M_2$ contains only the unmatched vertices from $V_n$.

In order to obtain a perfect matching, we recursively modify $E$ by choosing an unmatched vertex $a$ in $E$, and then either matching it with an appropriate vertex, or removing it from $E$. Specifically, if $N_{A_n}(a) \backslash V(M)$ is non-empty, there exists a vertex $a' \in N_{A_n}(a) \backslash V(M)$ such that we can add $a'$ to $E$ and $(a, a')$ to the matching $M$. Otherwise, $a$ is incident on only matched vertices, and we can safely remove it from $E$ without altering the fact that $E$ is a dominating set.

Our recursively modified $E$ (denoted by $E_{\text{rec}}$) is now a paired dominating set of $A_n$. Furthermore, in the worst case, we have doubled the unmatched vertices from $V_n$, and also doubled the vertices in $V_1,\ldots,V_{n-1}$. Thus,
\begin{align*}
2k_n \leq |E_{\text{rec}}| \leq 2\lvert V_1\lvert + \cdots + 2\lvert V_{n-1}\lvert+ \lvert M_1\lvert + 2\lvert M_2\lvert~.
\end{align*}
This implies that $2k_n - |C| \leq 2\lvert V_1\lvert + \cdots + 2\lvert V_{n-1}\lvert + |Z^n_{p}|$.
Since $2 k_n - |C| = 2|S_p|$, therefore,
$2|S_p| \leq 2\lvert V_1\lvert + \cdots + 2\lvert V_{n-1}\lvert + |Z^n_{p}|
\leq 2\lvert Z^1_p\lvert + \cdots + 2\lvert Z^{n-1}_p\lvert + |Z^n_{p}|$~.
\end{proof}

Using Claim \ref{claim_n_pr_dj_d}, we now see
\begin{align*}
2\displaystyle\sum\limits_{p=1}^{|B|} |S_{p} | & \leq
\displaystyle\sum\limits_{p=1}^{|B|} \Big(2\sum\limits_{j=1}^{n} |Z^j_{p}| - |Z^n_{p}|\Big)
= 2|D| - \displaystyle\sum\limits_{p=1}^{|B|} |Z^n_{p}| = 2|D| - |D_{n}|~.
\end{align*}

Therefore, $2|d^n_{n}| \leq 2|D| - |D_{n}|$.
Similarly, we can show that $2|d^i_{i}| \leq 2|D| - |D_{i}|$ for $i = 1, \ldots, n$. To conclude the proof, we see
\begin{align*}
\frac{1}{2^{n-1}}\displaystyle\prod\limits_{i=1}^{n} \gamma _{pr}(A_i) = 2(k_1\cdots k_n)
&\leq 2\displaystyle\sum\limits_{i=1}^{n}| d^i_{i}| \leq
2n|D| - \displaystyle\sum\limits_{i=1}^{n} |D_{i}| = (2n - 1)|D|~,\\
\displaystyle\prod\limits_{i=1}^{n} \gamma _{pr}(A_i) &\leq 2^{n-1}(2n - 1)\gamma _{pr}(A_1 \Box \cdots \Box A_n)~.
\end{align*}
\end{proof}

We conclude this section by observing that an improvement to the Hou-Jiang \cite{hou_jiang_pr_dom} inequality $\gamma_{pr}(G) \gamma _{pr}(H) \leq 7\gamma_{pr}(G \Box H)$ follows as a corollary:
\begin{cor_nonum}
Given graphs $G$ and $H$ containing no isolated vertices,
\begin{align*}
\gamma_{pr}(G) \gamma _{pr}(H) \leq 6 \gamma_{pr }(G \Box H)~.
\end{align*}
\end{cor_nonum}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgments} The authors would like to acknowledge the support of NSF-CMMI-0926618, the Rice University VIGRE program (NSF DMS-0739420 and EMSW21-VIGRE), and the Global Initiatives Fund (Brown School of Engineering at Rice University), under the aegis of SURGE (Summer Undergraduate Research Grant for Excellence), a joint program with the IIT Kanpur and the Rice Center for Engineering Leadership. Additionally, the authors acknowledge the support of NSF DSS-0729251, DSS-0240058, and the Defense Advanced Research Projects Agency
under Award No. N66001-10-1-4040. Finally, the authors would like to thank the anonymous referees for their careful reading and insightful comments which greatly simplified the presentation of the proof.

%Keerti Choudhary was supported by the Global Initiatives Fund at 
%Rice's Brown School of Engineering, under the aegis of SURGE,
%an undergraduate research program at IIT Kanpur and RCEL,
%the Rice Center for Engineering Leadership.

% code for adding to source control
%svn import KT https://cvs.caam.rice.edu:3129/svn/hicks_workgroup/Papers/Keerti/trunk -m "First Import"
%svn checkout https://cvs.caam.rice.edu:3129/svn/hicks_workgroup/Papers/Keerti/trunk Keerti
%svn propset svn:eol-style native *
%>  sm19
%>  h7GZtv3^

%\bibliography{b1}
\bibliographystyle{plain}

%\bibitem{raz}
%A. Razborov. Lower bounds for the polynomial calculus. {\em Computational Complexity}, 7:291--324, 1998.
%\bibliography{vizing}


\begin{thebibliography}{1}

\bibitem{viz_survey_2009}
B.~Bre\u{s}ar, P.~Dorbec, W.Goddard, B.Hartnell, M.Henning, S.Klav\u{z}ar, and
  D.Rall.
\newblock Vizing's conjecture: A survey and recent results.
\newblock {\em Journal of Graph Theory}, 69(1):46--76, 2012.

\bibitem{rall_pr}
B.~Bre\u{s}ar, M.~A. Henning, and D.~F. Rall.
\newblock Paired-domination of {C}artesian products of graphs.
\newblock {\em Utilitas Mathematica}, 73:255--265, 2007.

\bibitem{viz_clark_suen}
W.~Clark and S.~Suen.
\newblock An inequality related to {V}izing's conjecture.
\newblock {\em Electronic Journal of Combinatorics}, 7:N4, 2000.

\bibitem{ho_total_dom}
P.~T. Ho.
\newblock A note on the total domination number.
\newblock {\em Utilitas Mathematica}, 77:97--100, 2008.

\bibitem{hou_jiang_pr_dom}
X.~M. Hou and F.~Jiang.
\newblock Paired domination of {C}artesian products of graphs.
\newblock {\em Journal of Mathematical Research \& Exposition}, 30(1):181--185,
  2010.

\end{thebibliography}


\end{document}
