% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.19}{24(1)}{2017} \usepackage{amsthm,amsmath,amssymb} \usepackage{graphicx} \usepackage{tikz} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \newcommand{\gpr}{\gamma_{\rm pr}} \newcommand{\cB}{{\cal B}} \newcommand{\smallqed}{{\tiny ($\Box$)}} \newcommand{\barx}{\overline{x}} \newcommand{\barz}{\overline{z}} \newcommand{\barv}{\overline{v}} \newcommand{\bary}{\overline{y}} \newcommand{\barw}{\overline{w}} \newcommand{\barT}{\overline{T}} \newcommand{\barTX}{\overline{T}_{_X}} \newcommand{\tr}{\gamma_{\rm tr}} \newcommand{\gt}{\gamma_t} \newcommand{\cartprod}{\,\square\,} \def \HG {H_{_G}} \def \HGc {H_{_G}^{c}} \def \HX {H_{_X}} \def \HY {H_{_Y}} \def \eX {e_{_X}} \def \eY {e_{_Y}} \def \TX {T_{_X}} \def \TXc {T_{_X}^c} \newenvironment{unnumbered}[1]{\trivlist \item [\hskip \labelsep {\bf #1}]\ignorespaces\it}{\endtrivlist} % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\title{(Total) Domination in Prisms} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address %\author{ %Jernej Azarija $^{a,b}$ %\and %Michael A. Henning $^{c}$ %\and %Sandi Klav\v zar $^{a,b,d}$ %} \title{\bf (Total) Domination in Prisms} %\author{Jernej Azarija\thanks{Part of this research was done while this author was a postdoctoral researcher at LIMOS, Universit\'e Blaise Pascal, Clermont-Ferrand, France.} \qquad Michael A. Henning\\ %\small Department of Pure and Applied Mathematics\\[-0.8ex] %\small University of Johannesburg\\[-0.8ex] %\small Auckland Park, 2006 South Africa\\ %\small\tt florent.foucaud@gmail.com,mahenning@uj.ac.za\\ %} \author{Jernej Azarija\\ \small Faculty of Mathematics and Physics \\[-0.8ex] \small University of Ljubljana, Slovenia \\ \small Institute of Mathematics, Physics and Mechanics\\[-0.8ex] \small University of Ljubljana, Slovenia \\ \small\tt jernej.azarija@gmail.com\\ \and Michael A. Henning\\ \small Department of Pure and Applied Mathematics\\[-0.8ex] \small University of Johannesburg\\[-0.8ex] \small Auckland Park, 2006 South Africa\\ \small\tt mahenning@uj.ac.za \\ \and Sandi Klav\v zar\\ \small Faculty of Mathematics and Physics \\[-0.8ex] \small University of Ljubljana, Slovenia \\ \small Institute of Mathematics, Physics and Mechanics\\[-0.8ex] \small University of Ljubljana, Slovenia \\ \small Faculty of Natural Sciences and Mathematics\\[-0.8ex] \small University of Maribor, Slovenia\\ \small\tt sandi.klavzar@fmf.uni-lj.si\\ } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Jul 6, 2016}{Jan 16, 2017}{Feb 3, 2017}\\ \small Mathematics Subject Classifications: 05C69, 91C65, 05C76, 94B65} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} Using hypergraph transversals it is proved that $\gt(Q_{n+1}) = 2\gamma(Q_n)$, where $\gt(G)$ and $\gamma(G)$ denote the total domination number and the domination number of $G$, respectively, and $Q_n$ is the $n$-dimensional hypercube. More generally, it is shown that if $G$ is a bipartite graph, then $\gt(G \square K_2) = 2\gamma(G)$. Further, we show that the bipartiteness condition is essential by constructing, for any $k \ge 1$, a (non-bipartite) graph $G$ such that $\gamma_t(G\square K_2) = 2\gamma(G) - k$. Along the way several domination-type identities for hypercubes are also obtained. % keywords are optional \bigskip\noindent \textbf{Keywords:} domination; total domination; hypercube; Cartesian product of graphs; covering codes; hypergraph transversal \end{abstract} \section{Introduction} Domination and total domination in graphs are very well studied in the literature, here we study these concepts in prisms of graphs, in particular in hypercubes. To determine the domination number $\gamma$ of the $n$-dimensional hypercube $Q_n$, is a fundamental problem in coding theory, computer science, and of course in graph theory. In coding theory, the problem equivalent to the determination of $\gamma(Q_n)$ is to find the size of a minimal covering code of length $n$ and covering radius $1$. In computer science, different distribution type problems on interconnection networks can be modelled by domination invariants, where hypercubes in turn form a central model for interconnection networks. To determine $\gamma(Q_n)$ turns out to be an intrinsically difficult problem. To date, exact values are only known for $n \le 9$. These results are summarized in Table~\ref{table:hypercubes}. \begin{table}[ht!] \label{table:hypercubes} \begin{center} \begin{tabular}{|c|cccccccccc|} \hline \textit{n} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline\hline $\gamma(Q_n)$ & 1 & 2 & 2 & 4 & 7 & 12 & 16 & 32 & 62 & 107-120 \\ \hline \end{tabular} \end{center} \caption{Domination numbers of hypercubes up to dimension $10$} \end{table} We have checked these values by formulating an integer linear program and solving it with CPLEX. The result $\gamma(Q_9) = 62$ due to {\"O}sterg{\aa}rd and Blass~\cite{ostergard-2001} actually presented a breakthrough back in 2001. The value of $\gamma(Q_{10})$ is currently unknown, see~\cite{bertolo-2004} for the present best lower bound as given in Table~\ref{table:hypercubes} and~\cite{keri-2005} for the present best upper bound. Total domination $\gamma_t$ is, besides classical domination, among the most fundamental concepts in domination theory. It has in particular been extensively investigated on Cartesian product graphs (cf.\ \cite{choudhary-2013, henning-2005, lu-2010}), which was in a great part motivated by the famous Vizing's conjecture (see the survey~\cite{bresar-2012} and recent papers~\cite{bresar-2015, gonzales-yero-2015}). Specifically, $\gamma_t(Q_n)$ was recently investigated in the thesis~\cite{verstraten-2014} under the notion of a {\em binary covering code of empty spheres of length $n$ and radius $1$}. In particular, values $\gamma_t(Q_n)$ for $n \leq 10$ were computed and some bounds established. These exact values intrigued us to wonder whether there exists some general relation between the domination number and the total domination number in hypercubes. From our perspective it is utmost important that $Q_n$ can be represented as the $n^{\rm th}$ power of $K_2$ with respect to the Cartesian product operation $\cartprod$, that is, $Q_1 =K_2$ and $Q_n = Q_{n-1} \cartprod K_2$ for $n \ge 2$. Our immediate aim in this paper is to prove that $\gt(Q_{n+1}) = 2\gamma(Q_n)$ holds for all $n \ge 1$. For this purpose, we prove the following much more general result that the total domination number of a bipartite prism of a graph $G$ is equal to twice the domination number of $G$. \begin{theorem} \label{t:prism} If $G$ is a bipartite graph, then $$\gt(G \cartprod K_2) = 2\gamma(G)\,.$$ \end{theorem} Since $Q_n$, $n \ge 1$, is a bipartite graph, as a special case of Theorem~\ref{t:prism} we note that $\gt(Q_{n+1}) = 2\gamma(Q_n)$. Our second aim is to show that the bipartiteness condition in the statement of Theorem~\ref{t:prism} is essential. For this purpose, we prove the following result. \begin{theorem} \label{t:nonbipartite} For each integer $k \ge 1$, there exists a connected graph $G_k$ satisfying \[ 2\gamma(G_k) - \gt(G_k \cartprod K_2) = k. \] \end{theorem} We proceed as follows. In the next section concepts used throughout the paper are introduced and known facts and results needed are recalled. In particular, the state of the art on $\gamma(Q_n)$ is surveyed. In Section~\ref{sec:proof-of-main}, Theorem~\ref{t:prism} is proved and several of its consequences listed. A proof of Theorem~\ref{t:nonbipartite} is given in Section~\ref{sec:proof-of-non-bipartite}. We conclude the paper with some open problems. In particular we conjecture that the equality in Theorem~\ref{t:prism} holds for almost all graphs. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Preliminaries} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. The \emph{order} of $G$ is denoted by $n(G) = |V(G)|$. The \emph{open neighborhood} of a vertex $v$ in $G$ is $N_G(v) = \{u \in V(G) \, | \, uv \in E(G)\}$ and the \emph{closed neighborhood of $v$} is $N_G[v] = \{v\} \cup N_G(v)$. The path and the cycle on $n$ vertices are denoted by $P_n$ and $C_n$, respectively. For graphs $G$ and $H$, the \emph{Cartesian product} $G \cartprod H$ is the graph with vertex set $V(G) \times V(H)$ where vertices $(u_1,v_1)$ and $(u_2,v_2)$ are adjacent if and only if either $u_1 = u_2$ and $v_1v_2 \in E(H)$ or $v_1 = v_2$ and $u_1u_2 \in E(G)$. If $(u,v)\in V(G\cartprod H)$, then the subgraph of $G\cartprod H$ induced by the vertices of the form $(u,x)$, $x\in V(H)$, is isomorphic to $H$; it is called the {\em $H$-layer} (through $(u,v)$). Analogously $G$-layers are defined. The \emph{prism} of a graph $G$ is the graph $G \cartprod K_2$. Note that $G \cartprod K_2$ contains precisely two $G$-layers. Further, if $G$ is a bipartite graph, then we call the prism $G \cartprod K_2$ the \emph{bipartite prism} of $G$. As already mentioned in the introduction, $Q_n$ is a (bipartite) prism because $Q_n = Q_{n-1}\cartprod K_2$. A \emph{dominating set} of a graph $G$ is a set $S$ of vertices of $G$ such that every vertex in $V(G) \setminus S$ is adjacent to at least one vertex in $S$, while a \emph{total dominating set} of $G$ is a set $S$ of vertices of $G$ such that every vertex in $V(G)$ is adjacent to at least one vertex in $S$. The \emph{domination number} of $G$, denoted by $\gamma(G)$, is the minimum cardinality of a dominating set of $G$ and the \emph{total domination number} of $G$, denoted by $\gt(G)$, is the minimum cardinality of a total dominating set of $G$. We refer to the books~\cite{haynes-1988, HeYe_book} for more information on the domination number and the total domination number, respectively. The values $\gamma(Q_7) = 16$ and $\gamma(Q_8) = 32$ also follow from the following result which gives exact values for two infinite families of hypercubes. \begin{theorem}{\rm(\cite{harary-1993,wee-1988})} \label{thm:infinite-families} If $k\ge 1$, then $\gamma(Q_{2^k-1}) = 2^{2^k-k-1}$ and $\gamma(Q_{2^k}) = 2^{2^k-k}$. \end{theorem} The first assertion of Theorem~\ref{thm:infinite-families} is based on the fact that hypercubes $Q_{2^k-1}$ contain perfect codes, cf.~\cite{harary-1993}. Since the domination number of a graph with a perfect code is equal to the size of such a code, the assertion follows. Knowing the existence of such codes, by the divisibility condition one immediately infers that $Q_n$ contains a perfect code if and only if $n=2^k-1$ for some $k\ge 1$. Lee~\cite[Theorem 3]{lee-2001} further proved that this is equivalent to the fact that $Q_n$ is a regular covering of the complete graph $K_{n+1}$. The second assertion of Theorem~\ref{thm:infinite-families} is due to van Wee~\cite{wee-1988}. Related aspects of domination in hypercubes were investigated in~\cite{weichsel-1994}. A set $S$ of vertices in $G$ is a \emph{paired}-\emph{dominating set} if every vertex of $G$ is adjacent to a vertex in $S$ and the subgraph induced by $S$ contains a perfect matching (not necessarily as an induced subgraph). The minimum cardinality of a paired-dominating set of $G$ is the \emph{paired-domination number} of $G$, denoted $\gpr(G)$. A survey on paired-domination in graphs can be found in~\cite{Desor-2014}. By definition every paired-dominating set is a total dominating set, and every total dominating set is a dominating set. Hence we have the following result first observed by Haynes and Slater~\cite{HaSl98}. \begin{observation}{\rm(\cite{HaSl98})} \label{ob:2} For every isolate-free graph $G$, $\gamma(G) \le \gamma_t(G) \le \gpr(G)$. \end{observation} A \emph{total restrained dominating set} of $G$ is a total dominating set $S$ of $G$ with the additional property that every vertex outside $S$ has a neighbor outside $S$; that is, $G[V(G) \setminus S]$ contains no isolated vertex. The \emph{total restrained domination number} of $G$, denoted $\tr(G)$, is the minimum cardinality of a total restrained dominating set. The concept of total restrained domination in graphs was introduced by Telle and Proskurowksi~\cite{TePr97} as a vertex partitioning problem. By definition every total restrained dominating set if a total dominating set, implying the following observation. \begin{observation}{\rm(\cite{HaSl98})} \label{ob:3} For every isolate-free graph $G$, $\gt(G) \le \tr(G)$. \end{observation} The \emph{open neighborhood hypergraph}, abbreviated ONH, of $G$ is the hypergraph $H_G$ with vertex set $V(H_G) = V(G)$ and with edge set $E(H_G) = \{ N_G(x) \mid x \in V(G) \}$ consisting of the open neighborhoods of vertices in $G$. The \emph{closed neighborhood hypergraph}, abbreviated CNH, of $G$ is the hypergraph $H_G^c$ with vertex set $V(H_G^c) = V(G)$ and with edge set $E(H_G) = \{ N_G[x] \mid x \in V(G) \}$ consisting of the closed neighborhoods of vertices in $G$. A subset $T$ of vertices in a hypergraph $H$ is a \emph{transversal} (also called \emph{vertex cover} or \emph{hitting set}) if $T$ has a nonempty intersection with every hyperedge of $H$. The \emph{transversal number} $\tau(H)$ of $H$ is the minimum size of a transversal in $H$. A transversal of size~$\tau(H)$ is called a $\tau(H)$-set. The transversal number of the ONH of a graph is precisely the total domination number of the graph, while the transversal number of the CNH of a graph is precisely the domination number of the graph. We state this formally as follows. \begin{observation} \label{ob:1} If $G$ is a graph, then $\gt(G) = \tau(\HG)$ and $\gamma(G) = \tau(\HGc)$. \end{observation} We shall also need the following result from~\cite{HeYe08} (see also~\cite{HeYe_book}). \begin{theorem}{\rm (\cite{HeYe08})} \label{thm_ONH} The ONH of a connected bipartite graph consists of two components {\rm (}which are induced by the two partite sets of the graph{\rm )}, while the ONH of a connected graph that is not bipartite is connected. \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Proof of Theorem~\ref{t:prism} and its Consequences} \label{sec:proof-of-main} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this section, we first present a proof of Theorem~\ref{t:prism}. Recall its statement. \bigskip \noindent \textbf{Theorem~\ref{t:prism}} \emph{If $G$ is a bipartite graph, then $\gt(G \cartprod K_2) = 2\gamma(G)$.} \bigskip \proof Note first that $K_1\cartprod K_2 = K_2$, hence the assertion of the theorem holds for $G=K_1$. Since we can apply the result to each component of the bipartite graph $G$, we may assume that $G$ is connected. Hence in the rest of the proof, let $G$ be a connected bipartite graph of order at least $2$. Further, for notational convenience let $F$ denote the prism $G \cartprod K_2$ throughout the proof; that is, $F = G \cartprod K_2$. Let $G_1$ and $G_2$ be the $G$-layers of $F$, and let $V_i = V(G_i)$ for $i \in [2]$. For notational convenience, for each vertex $v$ in $G_1$ we denote the corresponding vertex in $G_2$ that is adjacent to $v$ in $F$ by $v'$. Thus, the set $\cup_{v \in V_1} \{vv'\}$ of edges between $V_1$ and $V_2$ in $F$ forms a perfect matching in $F$. Since $G$ is a bipartite graph, $F$ is bipartite as well. Let $X$ and $Y$ be the partite sets of $F$. If $w \in \{v,v'\}$ for some vertex $v \in V_1$, then we define the \emph{complement} of the vertex $w$ to be the vertex $\barw \in \{v,v'\} \setminus \{w\}$. We note that if $w \in V_{3-i}$, then $\barw \in V_i$ for $i \in [2]$. Further, we note that $w$ and $\barw$ belong to different partite sets of $F$. Let $H$ be the ONH of $F$. By Theorem~\ref{thm_ONH}, $H$ consists of two components that are induced by the two partite sets, $X$ and $Y$, of $F$. Let $\HX$ and $\HY$ be the two components of $H$, where $V(\HX) = X$ and $V(\HY) = Y$. We note that each hyperedge in $\HX$ and $\HY$ corresponds to the open neighborhood of some vertex in $Y$ and some vertex in $X$, respectively, in $F$. For each vertex $w$ in $F$, let $e_w$ be the associated hyperedge in $H$; that is, $e_w = N_F(w)$. We proceed further with the following series of claims. \begin{claim} \label{claim:1} The hypergraphs $\HX$ and $\HY$ are isomorphic. \end{claim} \proof Let $f \colon X \to Y$ be the function that assigns to each vertex $x \in X$ the vertex $\barx \in Y$. Then, $f$ is a bijection between the vertex set of $\HX$ and $\HY$. We show that the bijection $f$ is an isomorphism between the hypergraphs $\HX$ and $\HY$. We first show that for every hyperedge $e$ in $\HX$, the image $f(e) := \{f(z) \mid z \in e\}$ of $e$ in $f$ is a hyperedge in $\HY$, and conversely. Let $e$ be an arbitrary hyperedge in $\HX$. Thus, $e = e_w = N_F(w)$ for some vertex $w \in Y$. We claim that the image of $e$ is $N_F(\barw)$; that is, we claim that the image of $e = e_w$ is precisely the hyperedge in $\HY$ associated with the vertex $\barw \in X$. Without loss of generality, we may assume that $w \in V_1 \cap Y$. For an arbitrary vertex $z \in e$, either $z = \barw$ or $z \in N_{G_1}(w)$. If $z = \barw$, then $f(z) = w \in N_F(\barw)$. If $z \in N_{G_1}(w)$, then $f(z) = \barz \in N_{G_2}(\barw) \subset N_F(\barw)$. In both cases, $z \in N_F(\barw)$, implying that $f(e) \subseteq N_F(\barw)$. Conversely, interchanging the role of $X$ and $Y$, we have that $f(e) \supseteq N_F(\barw)$. Thus, $f(e) = N_F(\barw)$. %We show next that each hyperedge of $\HY$ can be obtained as an image. Suppose that $\eY$ is a hyperedge of $\HY$. Thus, $\eY = e_x = N_F(x)$ for some vertex $x \in X$. Analogously as before, $f(\eY) = N_F(\barx)$ is precisely the hyperedge in $\HX$ associated with the vertex $\barx \in Y$. Thus, the bijective function $f$ preserves adjacency, implying that $\HX$ and $\HY$ are isomorphic.~\smallqed \begin{claim} \label{claim:2} $\gt(F) = 2\tau(\HX)$. \end{claim} \proof By Observation~\ref{ob:1}, $\gt(F) = \tau(H) = \tau(\HX) + \tau(\HY)$. By Claim~\ref{claim:1}, $\tau(\HX) = \tau(\HY)$, and so $\gt(F) = 2\tau(\HX)$.~\smallqed \begin{claim} \label{claim:3} $\gt(F) \le 2\gamma(G)$. \end{claim} \proof Let $D$ be a minimum dominating set in $G$, and let $D_1$ and $D_2$ be the copies of $G$ in $G$-layers $G_1$ and $G_2$, respectively. Clearly, $v \in D_1$ if and only if $v' \in D_2$. The set $D_1 \cup D_2$ is a total dominating set of $F$, and so $\gt(F) \le |D_1 \cup D_2| = 2|D| = 2\gamma(G)$.~\smallqed \begin{claim} \label{claim:4} $\gamma(G) \le \tau(\HX)$. \end{claim} \proof Let $H^c$ be the CNH of $G$. By Observation~\ref{ob:1}, $\gamma(G) = \tau(H^c)$. We show that $\tau(H^c) \le \tau(\HX)$. Let $\TX$ be a minimum transversal in $\HX$, and so $|\TX| = \tau(\HX)$. We now define the set $\TXc$ as follows. For each vertex $v \in \TX$, we add $v$ to $\TXc$ if $v \in V_1$, otherwise if $v \in V_2$, we add $\barv$ to $\TXc$. We show that $\TXc$ is a transversal in $H^c$. Let $e$ be an arbitrary hyperedge in $H^c$. Thus, $e = N_F[w]$ for some vertex $w$ in $F$. We may assume without loss of generality that $w \in V_1$. Thus, $\barw = w' \in V_2$. Suppose that $w \in Y$. In this case, the hyperedge $e_w = N_F(w) = e \setminus \{w\}$ is a hyperedge of $\HX$ and is therefore covered by some vertex, say $z$, of $\TX$. If $z = \barw$, then $\barw \in V_2$ and $w \in \TXc$. If $z \ne \barw$, then $z \in e_w \setminus \{\barw\} \subset V_1$ and $z \in \TXc$. In both cases, the hyperedge $e$ is covered by a vertex in $\TXc$. Suppose that $w \in X$, and so $\barw \in Y \cap V_2$. In this case, the hyperedge $e_{\barw} = N_F(\barw)$ is a hyperedge of $\HX$ and is therefore covered by some vertex, say $z$, of $\TX$. If $z = w$, then since $w \in V_1$, the vertex $w \in \TXc$. If $z \ne \barw$, then $z \in e_{\barw} \setminus \{w\} \subset V_2$ and $\barz \in \TXc$. However, since $z \in e_{\barw}$, we note that $\barz \in e_{w}$. Thus in both cases, the hyperedge $e$ is covered by a vertex in $\TXc$. Thus, whenever $w \in X$ or $w \in Y$, the hyperedge $e$ is covered by a vertex in $\TXc$. Since $e$ is an arbitrary hyperedge of $H^c$, this implies that $\TXc$ is a transversal of $H^c$, and therefore that $\tau(H^c) \le |\TXc| = |\TX| = \tau(\HX)$.~\smallqed \medskip We now return to the proof of Theorem~\ref{t:prism} one final time. By Claims~\ref{claim:2},~\ref{claim:3}, and~\ref{claim:4}, the following holds. $$2\tau(\HX) \stackrel{{\rm Claim~\ref{claim:2}}}{=} \gt(F) \stackrel{{\rm Claim~\ref{claim:3}}}{\le} 2\gamma(G) \stackrel{{\rm Claim~\ref{claim:4}}}{\le} 2\tau(\HX)\,.$$ Consequently, we must have equality throughout the above inequality chain. In particular, $\gt(F) = 2\gamma(G)$. This completes the proof of Theorem~\ref{t:prism}.\qed \medskip As an immediate consequence of Theorem~\ref{t:prism} we state that the problems of determining the domination number and the total domination number of hypercubes are equivalent in the following sense: \begin{corollary} \label{cor:hypercubes} If $n\ge 1$, then $\gamma_t(Q_{n+1}) = 2\gamma(Q_n)$. \end{corollary} Combining Corollary~\ref{cor:hypercubes} with Theorem~\ref{thm:infinite-families} we also deduce the following result: \begin{corollary} \label{cor:infinite-total} If $k\ge 1$, then $\gamma_t(Q_{2^k+1}) = 2^{2^k-k+1}$ and $\gamma_t(Q_{2^k}) = 2^{2^k-k}$. \end{corollary} While the first assertion of Corollary~\ref{cor:infinite-total} appears to be new, the second assertion goes back to Johnson~\cite{johnson-1972}, see also~\cite[Theorem 1(b)]{weakley-2006}. As another consequence of Theorem~\ref{t:prism}, we have the following result. \begin{corollary} \label{cor:1} If $G$ is a bipartite graph, then $$\gt(G \cartprod K_2) = \gpr(G \cartprod K_2) = \tr(G \cartprod K_2)\,.$$ \end{corollary} \proof For notational convenience, we let $F = G \cartprod K_2$. As shown in the proof of Claim~\ref{claim:3} in Theorem~\ref{t:prism}, if $D_1$ is a minimum dominating set in $G_1$, and $D_2 = \{v' \mid v \in D_1\}$, then the set $D^* = D_1 \cup D_2$ is a total dominating set of $F$. We note that $D^*$ is also a paired-dominating set of $F$. Further, $|D^*| = 2\gamma(G)$. By Observation~\ref{ob:2} and Theorem~\ref{t:prism}, this implies that $$\gt(F) \le \gpr(F) \le |D^*| = 2\gamma(G) = \gt(F)\,.$$ Consequently, we must have equality throughout the above inequality chain. In particular, $\gt(F) = \gpr(F)$. % We note that $D^*$ is also a total restrained dominating set of $F$. Thus, by Observation~\ref{ob:3}, $\gt(F) \le \tr(F) \le |D^*| = 2\gamma(G) = \gt(F)$, implying that $\gt(F) = \tr(F)$. \qed As a special case of Theorem~\ref{t:prism} and Corollary~\ref{cor:1}, we have the following result. \begin{corollary} \label{cor:2} If $n \ge 1$, then $\gt(Q_n) = \gpr(Q_{n}) = \tr(Q_{n})$. \end{corollary} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Proof of Theorem~\ref{t:nonbipartite}} \label{sec:proof-of-non-bipartite} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this section, we consider general prisms and show that the bipartiteness condition in the statement of Theorem~\ref{t:prism} is essential. First we recall the trivial lower bound on the total domination number of a graph in terms of the maximum degree of the graph: If $G$ is a graph of order $n$ and maximum degree~$\Delta$ with no isolated vertex, then $\gt(G) \ge n/\Delta$, cf.~\cite[Theorem 2.11]{HeYe_book}. \begin{proposition} \label{prop:1} If $\ell \ge 1$, then $\gt(C_{6\ell +1}\cartprod K_2) = 2\gamma(C_{6\ell +1}) - 1$. \end{proposition} \proof Let $G \cong C_{6\ell+1}$ for some integer $\ell \ge 1$. Then, $\gamma(G) = \lceil n(G)/3 \rceil = 2\ell + 1$. For notational convenience, we let $F = G \cartprod K_2$. We show that $\gt(F) = 4\ell+1$. Let $G_1$ and $G_2$ be the $G$-layers of $F$, where $G_1$ is the cycle $u_1u_2 \ldots u_{6\ell+1}u_1$ and $G_2$ is the cycle $v_1v_2 \ldots v_{6\ell+1}v_1$, and where $u_iv_i \in E(G)$. The set \[ S = \left( \bigcup_{i=0}^{\ell-1} \{u_{6i+1},u_{6i+2}, v_{6i+4},v_{6i+5} \} \right) \cup \{u_{6\ell+1}\} \] \noindent is a total dominating set of $F$, implying that $\gt(F) \le |S| = 4\ell + 1$. Conversely, since $F$ is a cubic graph of order~$12\ell + 2$, the trivial lower bound on the total domination number of $F$ is given by $\gt(F) \ge (12\ell+2)/3$, implying that $\gt(F) \ge 4\ell+1$. Consequently, $\gt(F) = 4\ell+1$. As observed earlier, $\gamma(G) = 2\ell + 1$. Therefore, $\gt(F) = 2\gamma(G) - 1$.~\qed \medskip We show next that there are connected, non-bipartite graphs $G$ for which the difference $\gt(G \cartprod K_2) - 2\gamma(G)$ can be arbitrarily large. Recall the statement of Theorem~\ref{t:nonbipartite}. \medskip \noindent \textbf{Theorem~\ref{t:nonbipartite}} \emph{For each integer $k \ge 1$, there exists a connected graph $G_k$ satisfying $$ 2\gamma(G_k) - \gt(G_k \cartprod K_2) = k.$$ } \noindent \textbf{Proof.} For notational convenience, we let $F_k = G_k \cartprod K_2$. For $k = 1$, let $G_1 \cong C_7$. By Proposition~\ref{prop:1}, $\gt(F_1) = 2\gamma(G_1) - 1$. Hence, we assume in what follows that $k \ge 2$. For $i \in [k]$ and $\ell := i - 1$, let $Z_i$ be the $5$-cycle $v_{5\ell+1} v_{5\ell+2} v_{5\ell+4} v_{5\ell+5} v_{5\ell+3} v_{5\ell+1}$. Let $G_k$ be obtained from the disjoint union of the cycles $Z_1, \ldots, Z_k$ by adding the edges $v_{5j}v_{5j+1}$ for $j \in [k-1]$. By construction, $G_k$ is a connected graph of order $5k$. The following two claims determine the domination number of $G_k$ and total domination numbers of the prism $F_k$. \begin{unnumbered}{Claim~A} For $k \ge 2$, $\gamma(G_k) = 2k$. \end{unnumbered} \proof Every dominating set of $G_k$ contains at least two vertices from $V(Z_i)$ in order to dominate the vertices in $V(Z_i)$ for each $i \in [k]$, and so $\gamma(G_k) \ge 2k$. Conversely, every set consisting of two non-adjacent vertices from each set $V(Z_i)$ forms a dominating set of $G_k$, and so $\gamma(G_k) \le 2k$. Consequently, $\gamma(G_k) = 2k$.~\smallqed \begin{unnumbered}{Claim~B} For $k \ge 2$, $\gamma_t(F_k) = 3k$. \end{unnumbered} \proof Let $G_k^1$ and $G_k^2$ be the two copies of the graph $G_k$ in the prism $F_k$, where the vertex in $G_k^1$ and $G_k^2$ corresponding to the vertex $v_j$ in $G_k$ is labeled $x_j$ and $y_j$, respectively, for $j \in [5k]$. Thus, the set $\cup_{j=1}^{5k} \{x_jy_j\}$ of edges between $V(G_k^1)$ and $V(G_k^2)$ in $F_k$ forms a perfect matching in $F_k$. For $i \in [k]$ and $\ell := i - 1$, let \[ V_i = \bigcup_{j = 1}^5 \{x_{5\ell+j}, y_{5\ell+j} \}. \] When $k = 6$, the prism $F_k$ is illustrated in Figure~\ref{fig:prismG6}, where the vertices in $V_1$ are labelled. Let $S$ be an arbitrary total dominating set of $F_k$. For $i \in [k]$, let $S_i = S \cap V_i$. For $i \in [k]$ and $\ell := i - 1$, let \[ X_i = \bigcup_{j = 2}^4 \{x_{5\ell+j}\} \quad \mbox{and} \quad Y_i = \bigcup_{j = 2}^4 \{y_{5\ell+j}\} \] In order to totally dominate the vertices in the set $X_i$, we note that $|S_i| \ge 2$ for all $i \in [k]$. Suppose that $|S_i| = 2$ for some $i \in [k]$. If both vertices in $S_i$ belong to the same copy of $G_k$, say to $G_k^2$, then at least one vertex in $X_i$ is not totally dominated by $S$. If the vertices in $S_i$ belong to different copies of $G_k$, then at least two vertices in $X_i \cup Y_i$ are not totally dominated by $S$. Both cases produce a contradiction, implying that $|S_i| \ge 3$. Hence, \[ |S| = \sum_{i=1}^k |S_i| \ge 3k. \] Since $S$ is an arbitrary total dominating set of $F_k$, this implies that $\gt(F_k) \ge 3k$. To prove the converse, let $\ell := i - 1$ and \[ X = \bigcup_{i=1}^{\lfloor k/2 \rfloor } \{ x_{10\ell + 1}, x_{10\ell + 2}, x_{10i} \} \quad \mbox{and} \quad Y = \bigcup_{i=1}^{\lfloor k/2 \rfloor} \{ y_{10\ell + 5}, y_{10\ell + 6},y_{10\ell + 7} \}. \] If $k$ is even, let \[ D = (X \cup Y \cup \{x_{5k-1}\}) \setminus \{y_{5k-3}\}. \] If $k$ is odd, let \[ D = X \cup Y \cup \{x_{5k-4},y_{5k-1},y_{5k}\}. \] For $k = 6$, the set $D$ is illustrated by the darkened vertices in Figure~\ref{fig:prismG6}. In both cases, $D$ is a total dominating set of $F_k$, and $|D \cap V_i| = 3$ for each $i \in [k]$, implying that \[ \gt(F_k) \le |D| = \sum_{i=1}^k |D \cap V_i| = 3k. \] Consequently, $\gt(F_k) = 3k$.~\smallqed \medskip By Claim~A and Claim~B, for $k \ge 2$, $\gamma(G_k) = 2k$ and $\gt(F_k) = 3k$. This completes the proof of Theorem~\ref{t:nonbipartite}. \qed \begin{figure}[!ht] \centering \begin{tikzpicture}[scale=0.8,style=thick] \def\vr{3pt} \def\len{1} % define vertices \coordinate(x1) at (0,0); \coordinate(x2) at (0.5,0.7); \coordinate(x3) at (1.0,0); \coordinate(x4) at (1.5,0.7); \coordinate(x5) at (2.0,0); \coordinate(y1) at (0,2); \coordinate(y2) at (0.5,2.7); \coordinate(y3) at (1.0,2); \coordinate(y4) at (1.5,2.7); \coordinate(y5) at (2.0,2); \coordinate(x6) at (3,0); \coordinate(x7) at (3.5,0.7); \coordinate(x8) at (4.0,0); \coordinate(x9) at (4.5,0.7); \coordinate(x10) at (5.0,0); \coordinate(y6) at (3,2); \coordinate(y7) at (3.5,2.7); \coordinate(y8) at (4.0,2); \coordinate(y9) at (4.5,2.7); \coordinate(y10) at (5.0,2); \coordinate(x11) at (6,0); \coordinate(x12) at (6.5,0.7); \coordinate(x13) at (7.0,0); \coordinate(x14) at (7.5,0.7); \coordinate(x15) at (8.0,0); \coordinate(y11) at (6,2); \coordinate(y12) at (6.5,2.7); \coordinate(y13) at (7.0,2); \coordinate(y14) at (7.5,2.7); \coordinate(y15) at (8.0,2); \coordinate(x16) at (9,0); \coordinate(x17) at (9.5,0.7); \coordinate(x18) at (10.0,0); \coordinate(x19) at (10.5,0.7); \coordinate(x20) at (11.0,0); \coordinate(y16) at (9,2); \coordinate(y17) at (9.5,2.7); \coordinate(y18) at (10.0,2); \coordinate(y19) at (10.5,2.7); \coordinate(y20) at (11.0,2); \coordinate(x21) at (12,0); \coordinate(x22) at (12.5,0.7); \coordinate(x23) at (13.0,0); \coordinate(x24) at (13.5,0.7); \coordinate(x25) at (14.0,0); \coordinate(y21) at (12,2); \coordinate(y22) at (12.5,2.7); \coordinate(y23) at (13.0,2); \coordinate(y24) at (13.5,2.7); \coordinate(y25) at (14.0,2); \coordinate(x26) at (15,0); \coordinate(x27) at (15.5,0.7); \coordinate(x28) at (16.0,0); \coordinate(x29) at (16.5,0.7); \coordinate(x30) at (17.0,0); \coordinate(y26) at (15,2); \coordinate(y27) at (15.5,2.7); \coordinate(y28) at (16.0,2); \coordinate(y29) at (16.5,2.7); \coordinate(y30) at (17.0,2); % edges \draw (x1) -- (x2) -- (x4) -- (x5) -- (x3) -- (x1); \draw (y1) -- (y2) -- (y4) -- (y5) -- (y3) -- (y1); \draw (x6) -- (x7) -- (x9) -- (x10) -- (x8) -- (x6); \draw (y6) -- (y7) -- (y9) -- (y10) -- (y8) -- (y6); \draw (x11) -- (x12) -- (x14) -- (x15) -- (x13) -- (x11); \draw (y11) -- (y12) -- (y14) -- (y15) -- (y13) -- (y11); \draw (x16) -- (x17) -- (x19) -- (x20) -- (x18) -- (x16); \draw (y16) -- (y17) -- (y19) -- (y20) -- (y18) -- (y16); \draw (x21) -- (x22) -- (x24) -- (x25) -- (x23) -- (x21); \draw (y21) -- (y22) -- (y24) -- (y25) -- (y23) -- (y21); \draw (x26) -- (x27) -- (x29) -- (x30) -- (x28) -- (x26); \draw (y26) -- (y27) -- (y29) -- (y30) -- (y28) -- (y26); \foreach \i in {1,...,30} { \draw (x\i) -- (y\i); } \draw (x5) -- (x6); \draw (y5) -- (y6); \draw (x10) -- (x11); \draw (y10) -- (y11); \draw (x15) -- (x16); \draw (y15) -- (y16); \draw (x20) -- (x21); \draw (y20) -- (y21); \draw (x25) -- (x26); \draw (y25) -- (y26); % vertices \foreach \i in {1,...,30} { \draw(x\i)[fill=white] circle(\vr); } \foreach \i in {1,...,30} { \draw(y\i)[fill=white] circle(\vr); } \draw(x1)[fill=black] circle(\vr); \draw(x2)[fill=black] circle(\vr); % \draw(y5)[fill=black] circle(\vr); \draw(y6)[fill=black] circle(\vr); \draw(y7)[fill=black] circle(\vr); % \draw(x10)[fill=black] circle(\vr); \draw(x11)[fill=black] circle(\vr); \draw(x12)[fill=black] circle(\vr); % \draw(y15)[fill=black] circle(\vr); \draw(y16)[fill=black] circle(\vr); \draw(y17)[fill=black] circle(\vr); % \draw(x20)[fill=black] circle(\vr); \draw(x21)[fill=black] circle(\vr); \draw(x22)[fill=black] circle(\vr); % \draw(y25)[fill=black] circle(\vr); \draw(y26)[fill=black] circle(\vr); % \draw(x29)[fill=black] circle(\vr); \draw(x30)[fill=black] circle(\vr); % labels \draw(x1)node[below] {{\small $x_1$}}; \draw (0.6,0.35) node {{\small $x_2$}}; \draw(x3)node[below] {{\small $x_3$}}; \draw (1.4,0.35) node {{\small $x_4$}}; \draw(x5)node[below] {{\small $x_5$}}; \draw(-0.1,2.3) node {{\small $y_1$}}; \draw(y2)node[above] {{\small $y_2$}}; \draw(y3)node[above] {{\small $y_3$}}; \draw(y4)node[above] {{\small $y_4$}}; \draw(2.1,2.3) node {{\small $y_5$}}; \end{tikzpicture} \caption{The prism $G_6 \cartprod K_2$} \label{fig:prismG6} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Concluding Remarks} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let us say that a graph $G$ is {\em $\gamma_t$-prism perfect} if $\gamma_t(G \cartprod K_2) = 2\gamma(G)$. We have seen that all bipartite graphs are $\gamma_t$-prism perfect. It would certainly be interesting to characterize $\gamma_t$-prism perfect graphs in general, but this appears to be a challenging problem. Instead, one could try to characterize $\gamma_t$-prism perfect graphs within some interesting families of graphs, say triangle-free graphs. A computation shows that among the $11.117$ connected graphs of order $8$, precisely $297$ graphs are not $\gamma_t$-prism perfect. Similarly, there are $79.638$ graphs that are not $\gamma_t$-prism perfect among the $11.716.571$ connected graphs of order $9$. These computations led us to conjecture the following conjecture. \begin{conjecture} Almost all graphs are $\gamma_t$-prism perfect. \end{conjecture} With respect to the conjecture we refer to~\cite{glebov-2015} for the investigation of the behavior of the domination number in random graphs. Motivated by the construction presented in the proof of Theorem~\ref{t:nonbipartite} we wonder whether the following lower bound on the total domination number of prisms holds true. If so, then the construction implies that the bound is sharp. \begin{problem} Is it true that for any graph $G$, $\gamma_t(G \cartprod K_2) \ge \frac{3}{2}\gamma(G)$? \end{problem} One may be tempted to try to extend the presented results to additional Cartesian product graphs. We note that $\gamma(P_3) = 2$ and an easy computation gives $\gamma_t(P_3 \square K_3) = \gamma_t(P_3 \square P_3) = 4$. Similarly, $\gamma_t(P_3 \square K_4) = 4$ and $\gamma_t( P_3 \square P_4) = 6$, indicating that our result cannot be extended by a matter of parity. Moreover for all listed Cartesian products we were able to find pairs of bipartite graphs with the same domination number so that the total domination number of the respective Cartesian product differs. These examples give a strong evidence that the identity of Theorem~\ref{t:prism} cannot be generalized in ``obvious" directions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section*{Acknowledgements} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Research of Jernej Azaria was supported by the Slovenian Research Agency (research core funding Nos.\ J1-7110, P1-0297 and and N1-0043). Research of Michael A. Henning was supported in part by the South African National Research Foundation and the University of Johannesburg. Research of Sandi Klav\v zar was supported by the Slovenian Research Agency (research core funding Nos.\ J1-7110, P1-0297 and and N1-0043). The authors would also like to thank the anonymous referees, whose insightful comments improved the clarity and exposition of the paper. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \bibliographystyle{plain} % \bibliography{myBibFile} % If you use BibTeX to create a bibliography % then copy and past the contents of your .bbl file into your .tex file \begin{thebibliography}{10} \bibitem{bertolo-2004} R.~Bertolo, P.R.J.~{\"O}sterg{\aa}rd, and W.D.~Weakley, An updated table of binary/ternary mixed covering codes. \textit{J.\ Combin.\ Des.}\ 12:157--176, 2004. \bibitem{bresar-2015} B.~Bre\v sar, Vizing's conjecture for graphs with domination number 3---a new proof. \textit{Electron.\ J.\ Combin.}\ 22(3):\#P3.38, 2015. \bibitem{bresar-2012} B.~Bre\v sar, P.~Dorbec, W.~Goddard, B.L.~Hartnell, M.A.~Henning, S.~Klav\v zar, and D.F.~Rall, Vizing's conjecture: a survey and recent results. \textit{J.\ Graph Theory} 69:46--76, 2012. \bibitem{choudhary-2013} K.~Choudhary, S.~Margulies, and I.V.~Hicks, A note on total and paired domination of Cartesian product graphs. \textit{Electron.\ J.\ Combin.}\ 20(3):\#P25, 2013. \bibitem{Desor-2014} W. J. Desormeaux and M. A. Henning, Paired domination in graphs: A survey and recent results. \textit{Utilitas Mathematica} 94:101--166, 2014. \bibitem{glebov-2015} R.~Glebov, A.~Liebenau, and T.~Szab{\'o}, On the concentration of the domination number of the random graph. \textit{SIAM J.\ Discrete Math.}\ 29:1186--1206, 2015. \bibitem{gonzales-yero-2015} I.~Gonz\'alez Yero, Partial product of graphs and {V}izing's conjecture. \textit{Ars Math.\ Contemp.}\ 9:19--25, 2015. \bibitem{hammack-2011} R.~Hammack, W.~Imrich, and S.~Klav\v zar, \emph{Handbook of Product Graphs. Second Edition}. CRC Press, Boca Raton, FL, 2011. \bibitem{harary-1993} F.~Harary and M.~Livingston, Independent domination in hypercubes. \textit{Appl.\ Math.\ Lett.}\ 6:27--28, 1993. \bibitem{haynes-1988} T.W.~Haynes, S.T.~Hedetniemi, and P.J.~Slater, \emph{Fundamentals of Domination in Graphs}. Marcel Dekker, Inc., New York, 1998. \bibitem{HaSl98} T.W.~Haynes and P.J.~Slater, Paired domination in graphs. \textit{Networks} 32:199--206, 1998. \bibitem{henning-2005} M.A.~Henning and D.F.~Rall, On the total domination number of Cartesian products of graphs. \textit{Graphs Combin.}\ 21:63--69, 2005. \bibitem{HeYe08} M.A.~Henning and A.~Yeo, Hypergraphs with large transversal number and with edge sizes at least three. \textit{J.\ Graph Theory} 59:326--348, 2008. \bibitem{HeYe_book} M.A.~Henning and A.~Yeo, \emph{Total Domination in Graphs.} Springer Monographs in Mathematics, 2013. \bibitem{johnson-1972} S.M. Johnson, A new lower bound for coverings by rook domains. \textit{Utilitas Math.}\ 1:121--140, 1972. \bibitem{keri-2005} G.~K{\'e}ri and P.R.J.~{\"O}sterg{\aa}rd, Bounds for covering codes over large alphabets. \textit{Des.\ Codes Cryptogr.}\ 137:45--60, 2005. \bibitem{lee-2001} J.~Lee, Independent perfect domination sets in Cayley graphs. \textit{J.\ Graph Theory} 37:213--219, 2001. \bibitem{lu-2010} Y.~Lu and X.~Hou, Total domination in the Cartesian product of a graph and $K_2$ or $C_n$. \textit{Utilitas Math.}\ 83:313--322, 2010. \bibitem{kwon-2014} Y.S.~Kwon and J.~Lee, Perfect domination sets in Cayley graphs. \textit{Discrete Appl.\ Math.}\ 162:259--263, 2014. \bibitem{ostergard-2001} P.R.J.~{\"O}sterg{\aa}rd and U.~Blass, On the size of optimal binary codes of length 9 and covering radius~$1$. \textit{IEEE Trans.\ Inform.\ Theory} 47:2556--2557, 2001. \bibitem{TePr97} J.~Telle and A.~Proskurowski, Algorithms for vertex partitioning problems on partial $k$-trees. \textit{SIAM J.\ Discrete Math.}\ 10:529--550, 1997. \bibitem{verstraten-2014} K.P.F.~Verstraten, \emph{A Generalization of the Football Pool Problem.} Master thesis, Tilburg University, 2014, \url{https://oeis.org/A238305/a238305.pdf}. \bibitem{weakley-2006} W.D.~Weakley, Optimal binary covering codes of length $2^j$, \textit{J.\ Combin.\ Des.}\ 14:1--13, 2006. \bibitem{weichsel-1994} P.M.~Weichsel, Dominating sets in $n$-cubes, \textit{J.\ Graph Theory} 18:479--488, 1994. \bibitem{wee-1988} G.J.M. van Wee, Improved sphere bounds on the covering radius of codes. \textit{IEEE Trans.\ Inform.\ Theory} 34:237--245, 1988. \end{thebibliography} \end{document}