% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P3.38}{22(3)}{2015} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % 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} \newcommand{\RReal}{\mathbb{R}} \newcommand{\NNatural}{\mathbb{N}} \newcommand{\cp}{\mathbin{\Box}} % if needed include a line break (\\) at an appropriate place in the title %\title{\bf An elementary proof\\ of the reconstruction conjecture} \title{\bf Vizing's conjecture for graphs with \\ domination number 3 - a new proof} % 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{Bo\v{s}tjan Bre\v{s}ar\thanks{The author is also with the Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia, and is supported by the Slovenian Research Agency (ARRS) under the grant P1-0297.}\\ \small Faculty of Natural Sciences and Mathematics\\[-0.8ex] \small University of Maribor\\[-0.8ex] \small Slovenia\\ \small\tt bostjan.bresar@um.si } \date{\dateline{Apr 13, 2015}{Sep 11, 2015}{Sep 20, 2015}\\ \small Mathematics Subject Classifications: 05C69} \begin{document} \maketitle \begin{abstract} Vizing's conjecture from 1968 asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In this note we use a new, transparent approach to prove Vizing's conjecture for graphs with domination number 3; that is, we prove that for any graph $G$ with $\gamma(G)=3$ and an arbitrary graph $H$, $\gamma(G\cp H) \ge 3\gamma(H)$. \bigskip\noindent \textbf{Keywords:} Cartesian product; domination; Vizing's conjecture \end{abstract} \section{Introduction} The following long-standing conjecture \begin{conjecture}\label{VC}{\rm (\cite{V1963})} For every pair of finite graphs $G$ and $H$, \begin{equation}\label{VCeqn0} \gamma(G\cp H) \ge \gamma(G)\,\gamma(H), \end{equation} \end{conjecture} \noindent is arguably the most important open problem in graph domination. (As usually, $\gamma$ stands for the domination number, and $G\cp H$ is the standard notation for the Cartesian product of graphs $G$ and $H$.) The first extensive survey on Vizing's conjecture was published already in~1998~\cite{hr-1998}, and for a recent survey see~\cite{brdo-2012}. Although many partial results are known that prove inequality~(\ref{VCeqn0}) (or a weaker form of it) for several classes of graphs, the conjecture remains unsolved. As a side-effect of these approaches some new methods and concepts in domination theory have been developed. In particular, the conjecture motivated the study of different domination parameters in Cartesian products of graphs, and was one of the main motivations for the introduction of the rainbow domination~\cite{bhr-2008} and of the domination game~\cite{imagination}. One of the first partial results proving that inequality~(\ref{VCeqn0}) holds for a very special class of graphs was obtained by Barcalkin and German~\cite{bg-1979}. The proof in a clever way uses the simple idea of projecting the vertices in a dominating set of $G\cp H$ to $\gamma(G)$ copies of the graph $H$ in such a way that to each copy at least $\gamma(H)$ vertices are projected. A somewhat more sophisticated idea of the so-called double projection has been used by Clark and Suen~\cite{cs-2000} in their proof of the weaker version of (\ref{VCeqn0}), where the right side of the inequality is multiplied by $1/2$; cf.~\cite{wu-2013,st-2012} for recent improvements of this result, and~\cite{gy-2015} for another very recent approach to the conjecture. The best result so far in terms of domination numbers of factors due to Liang Sun~\cite{S2004} states that the conjectured inequality holds if one of the factors has domination number (at most) 3 and the other factor is arbitrary. By saying that a graph $G$ {\em satisfies Vizing's conjecture} we mean that for any other graph $H$ the conjectured inequality $\gamma(G\cp H) \ge \gamma(G)\,\gamma(H)$ holds; hence in this terminology, Liang Sun's result proves that all graph with domination number (at most) 3 satisfy Vizing's conjecture. However, the proof in~\cite{S2004} is very technical and a need for a more transparent proof of this result has been expressed for instance in~\cite{HaImKl}. In this paper we present a new proof of the result that graphs with domination number 3 satisfy Vizing's conjecture, see Theorem~\ref{thm:3}. The proof is based on the simple idea of projecting a dominating set of the product $G\cp H$ to three copies of $H$, so that projected vertices in each copy induce a dominating set of $H$ (where $G$ is a graph with domination number 3). The idea works because of a special rule that we impose on the projection maps. In the proof several cases appear, one of which needs somewhat deeper analysis. Nevertheless, we believe that the overall approach of the proof is transparent and not hard to follow, making it convenient for possible further generalizations and extensions. In the rest of this section we establish the notation, and present some preliminary observations needed in the proof of the main result, while Section~2 contains its proof. Let $G=(V(G),E(G))$ be a finite, simple graph. For subsets $A$ and $B$ of vertices of $G$, we say that $B$ \emph{dominates} $A$ (or $A$ {\em is dominated by} $B$) if $A \subseteq N[B]$; that is, if each vertex of $A$ is in $B$ or is adjacent to some vertex of $B$. The \emph{domination number} of $G$ is the smallest cardinality, denoted $\gamma(G)$, of a set that dominates $V(G)$. If $D$ dominates~$V(G)$, we will also say that $D$ dominates the graph $G$ and that $D$ is a \emph{dominating set} of $G$. The \emph{Cartesian product} $G\cp H$ of graphs $G$ and $H$ is the graph whose vertex set is $V(G) \times V(H)$. Two vertices $(g_1,h_1)$ and $(g_2,h_2)$ are adjacent in $G \cp H$ if either $g_1=g_2$ and $h_1h_2$ is an edge in $H$ or $h_1=h_2$ and $g_1g_2$ is an edge in $G$. For a vertex $g$ of $G$, the subgraph of $G\cp H$ induced by the set $\{ \, (g,h) \mid h\in H \,\}$ is called an \emph{$H$-fiber} and is denoted by $^g\!H$. Similarly, for $h \in H$, the \emph{$G$-fiber}, $G^h$, is the subgraph induced by $\{ \, (g,h) \mid g\in G \,\}$. We will make use of projection maps from the Cartesian product $G \cp H$ to one of the factors $G$ or $H$. The \emph{projection to $H$} is the map $p_H: V(G \cp H ) \to V(H)$ defined by $p_H(g,h)=h$. When $D$ is a dominating set of the product $G\cp H$, we will often say that $(g,h)\in D$ is projected to $h$ in $H_i$, by which we will indicate that $h$ is added to a dominating set that is being built in the copy $H_i$ of $H$. \bigskip In this note we prove the following result. \bigskip \begin{theorem} \label{thm:3} Let $G$ and $H$ be finite graphs, $\gamma(G)=3$, and $H$ is an arbitrary graph. Then \begin{equation}\label{VCeqn} \gamma(G\cp H) \ge 3\,\gamma(H). \end{equation} \end{theorem} \medskip We will use the following well-known observation. \begin{observation} \label{o:basic} Let $G$ be a graph that satisfies Vizing's conjecture, and let $G'$ be a spanning subgraph of $G$ such that $\gamma(G')=\gamma(G)$. Then $G'$ also satisfies Vizing's conjecture. \end{observation} Indeed, if $H$ is any graph, then \[\gamma(G')\gamma(H) = \gamma(G)\gamma(H) \le \gamma(G\cp H)\le \gamma(G'\cp H)\,.\] The last inequality holds since $G'\cp H$ is a spanning subgraph of $G \cp H$. Hence, to prove that Vizing's conjecture is satisfied by graphs $G$ with domination number 3 we may restrict in the proof only to graphs $G$ that are {\em edge-maximal} with respect to domination number (edge-maximal means that by adding any edge between two non-adjacent vertices in $G$ the domination number drops). \begin{observation} \label{o:edgemax} Let $G$ be a graph with $\gamma(G)=3$, which is edge-maximal with respect to domination number. Then there exists a dominating set $D=\{a,b,c\}$ of $G$ such that $N[a]\cup N[b]=V(G)\setminus\{c\}$. \end{observation} To see that Observation~\ref{o:edgemax} is correct, note that by adding an edge between two non-adjacent vertices $a$ and $c$ in $G$, the domination number of the resulting graph $G+ac$ is 2, and either $a$ or $c$ must be in a minimum dominating set of $G+ac$. Let $\{a,b\}$ be a dominating set of $G+ac$. But then in $G$ vertices $a$ and $b$ dominate every vertex except $c$. In the proof we will also use the following classical theorem from set theory (known as {\em Hall's marriage theorem}). Recall that a family of (nonempty) finite sets $\{S_1,\ldots,S_n\}$ has a {\em system of distinct representatives}, if there exists a set of their elements $\{x_1,\ldots,x_n\}$ such that $x_i\in S_i$ for all $i\in [n]$ (as usually, $[n]$ denotes the set $\{1,\ldots,n\}$). \begin{theorem} \label{thm:Hall} Let $\mathcal{S}=\{S_1,\ldots,S_n\}$ be a family of \emph{(}nonempty\emph{)} finite sets. There exists a system of distinct representatives of the sets from $\mathcal{S}$ if and only if for each subfamily $S_{i_1},\ldots,S_{i_k}$ of $\mathcal{S}$ the following \emph{(}Hall's condition\emph{)} holds:$$|S_{i_1}\cup\cdots\cup S_{i_k}|\ge k.$$ \end{theorem} \section{Proof of Theorem~\ref{thm:3}} Let $G$ be a (connected) graph with $\gamma(G)=3$, and let $I=\{v_1,v_2,v_3\}$ be a dominating set of $G$. By Observations~\ref{o:basic}~and~~\ref{o:edgemax} we may assume that $G$ is edge-maximal and that $N[v_1]\cup N[v_2]=V(G)\setminus\{v_3\}$. For any $i\in [3]=\{1,2,3\}$, let $P_i$ denote the set of external private neighbors of $v_i$ in $G$ with respect to $I$, that is $$P_i=\{x\in V(G)\setminus I\,:\,N(x)\cap I=v_i\}.$$ Note that $P_3=\varnothing$ and set $P=P_1\cup P_2$. Let $Q_i=P_i\cup\{v_i\}$, and $Q=Q_1\cup Q_2\cup Q_3$. Next, for any $S\subseteq [3]$, $|S|\ge 2$, $$P_S=\{x\in V(G)\setminus Q\,:\,N(x)\cap I=\{v_i\,|\,i\in S\}\}.$$ For instance, $P_{\{1,3\}}$ is the set of vertices that are adjacent to $v_1$ and $v_3$ and are not adjacent to $v_2$. Let $D$ be a dominating set of $G\cp H$. We will project vertices of $D$ to three copies of $H$, denoted by $H_1,H_2, H_3$. Each vertex of $D$ is allowed to project to only one vertex in only one copy of $H$; the set of projected vertices in the copy $H_i$ is denoted by $D_i$. We will prove that projections can be performed in such a way that each $D_i$ is a dominating set in $H_i$. If this is done, it clearly implies that $|D|\ge 3\gamma(H)$. The projections will be done in three steps (the third step is optional, depending on the structure of $G$ and of the dominating set of $G\cp H$, and makes some corrections to projections made in the first step). \smallskip In the {\bf first step} we project the vertices $(x,h)\in D$, where $x\in Q$ in the following natural way: if $x \in Q_i$ then we project $(x,h)$ to $h$ in the copy $H_i$ (Note that by {\em projecting} $(x,h)$ to $h$ in $H_i$ we mean that we put $h$ to the set $D_i$ of $H_i$.) \smallskip After the first step, we examine each fiber $G^h$ for $h\in V(H)$, and consider the copies of $h$ in all $H_i$ that are not yet dominated by the set $D_i$, constructed so far. We say that the pair $\{i,h\}$ is {\em vertically undominated} if $(Q_i\times N_H[h])\cap D=\varnothing$. Obviously in each fiber $G^h$ there are between zero and three such vertically undominated pairs $\{i,h\}$. \smallskip In the {\bf second step} we project the vertices $(x,h)\in D$, where $x\in V(G)\setminus Q$, in such a way that the following rule is obeyed: \smallskip {\bf (R)} if $x\in P_S$, where $S\subseteq [3]$, then there exists an $i\in S$ and a vertex $(y,h)$ from $D\cap G^h$, such that $(y,h)$ is projected to $h$ in the copy $H_i$. \smallskip We will say a vertex $(x,h)$ from $D\cap G^h$ is {\em free} if there exists another vertex $(y,h)\in D$, which is projected to $h$ in $H_i$, and $i\in S$, where $x\in P_S$. \medskip We distinguish 7 cases with respect to the following properties of the fibers $G^h$, for which not all copies of $h$ in $H_i$ are dominated by $D_i$. By {\bf Case $k/m$}, where $1\le m\le k\le 3$ we mean that in $G^h$ there are $k$ pairs $\{i,h\}$ that are vertically undominated, and that there are $m$ vertices in $((V(G)\setminus Q)\times \{h\})\cap D$. As it turns out, it can also happen that there is one pair $\{i,h\}$ that is vertically undominated, yet there are no vertices in $((V(G)\setminus Q) \times \{h\})\cap D$. This case will be denoted by {\bf Case $1/0$}. It will also become clear that the cases when $m>k$ can be easily translated to the case when $m=k$. In each of the cases we argue how the projection of the vertices from $G^h\cap D$ is performed in the second step, so that for each vertically undominated pair $\{i,h\}$, the vertex $h$ becomes dominated in $H_i$, and at the same time the rule (R) is obeyed for the projected vertices. The only exception, where the projections fail to achieve the desired goal, may appear in Case 2/1. This case is dealt with at the end, after all the projections of the second step are done in all the $G$-fibers, which fall under other cases. If such a problem in Case 2/1 appears, it leads to the third step in which some modifications of projections from the first step are perfomed. \bigskip \smallskip {\bf Case $1/0$.} As there are no vertices in $((V(G)\setminus Q) \times \{h\})\cap D$, it is clear that $\{3,h\}$ cannot be vertically undominated, because no vertex from $(P_1\cup P_2)\times\{h\}$ is adjacent to $(v_3,h)$. (Note that from the same reason, cases 3/0 and 2/0 are not possible.) Hence we may assume without loss of generality that $\{1,h\}$ is vertically undominated. Then $(v_1,h)$ and all $(u,h)$ for $u\in P_1$ must be dominated from $G^h\cap D$. In particular, the only way to dominate $(v_1,h)$ is from $I\times\{h\}$; more precisely, we infer that $(v_2,h)\in D$. In addition, to dominate a vertex $(u,h)$ for $u\in P_1$ there must exist a vertex $(v,h)\in D$ where $v\in P_2$. Now, as both vertices $(v_2,h)$ and $(v,h)$ are projected in the first step to the same vertex $h$ in $H_2$, we find that one of them is a free vertex. We project it to $h$ in $H_1$, and so $h$ is dominated in each of the three copies $H_i$. \smallskip {\bf Case $1/1$.} In this case exactly one $\{i,h\}$, $i\in [3]$ is vertically undominated, and there is one vertex from $(x,h)\in D$ with $x\not\in Q$. If $x$ is adjacent to $v_i$, then we can project $(x,h)$ to $h$ in $H_i$ by which the rule (R) is obeyed, and the proof in this case is done. On the other hand, if $x$ is not adjacent to $v_i$, then $i\in \{1,2\}$ because $(v_i,h)$ must be dominated within $G^h$ and $v_3$ is not adjacent to any vertex from $Q$. We may assume without loss of generality that $(v_1,h)$ is vertically undominated. This implies that $(v_2,h)\in D$, $v_2$ is adjacent to $v_1$, and $x\in P_{\{2,3\}}$. Hence the rule (R) is already obeyed for $(x,h)$ (with the vertex $(v_2,h)$ projected to $h$ in $H_2$) and so $(x,h)$ is free. We project it to $h$ in $H_1$, and so $h$ becomes dominated in $H_1$. \smallskip {\bf Case $2/2$.} Let $\{i,h\}$ and $\{j,h\}$ be vertically undominated, let $k$ be the unique index in $[3]\setminus \{i,j\}$, and let $(x,h),(y,h)\in D$ such that $x,y\not\in Q$. If none of $(v_i,h)$ and $(v_j,h)$ is dominated by $(v_k,h)$, then it is easy to see, that we can project $(x,h)$ and $(y,h)$ to the copies of $h$ in $H_i$ and $H_j$ in such a way that (R) is obeyed. Now, assume that at least one of $(v_i,h)$, $(v_j,h)$ is dominated by $(v_k,h)$, which is thus in $D$. Then each of the vertices $(x,h)$ and $(y,h)$ is either free (when it is adjacent to $(v_k,h)$), or it is in $P_{\{i,j\}}$. In either case we can project them to the copies of $h$ in $H_i$ and $H_j$, by which the proof of this case if complete. \smallskip {\bf Case $3/1$.} In this case $\{1,h\},\{2,h\}$ and $\{3,h\}$ are vertically undominated, and let $(x,h)$ be the unique vertex in $G^h\cap D$ (clearly $x\not\in Q$). We claim that in each of $P_{\{1,2\}}$, $P_{\{1,3\}}$, and $P_{\{2,3\}}$ there exists a vertex that is not adjacent to $x$. Indeed, if every vertex in, say $P_{\{1,2\}}$, were adjacent to $x$, then $\{x,v_3\}$ would be a dominating set of $G$, which is a contradiction with $\gamma(G)=3$. Let $u\in P_{\{1,2\}}$, $v\in P_{\{1,3\}}$, and $w\in P_{\{2,3\}}$ be vertices not adjacent to $x$. Hence $(u,h),(v,h),(w,h)$ are (vertically) dominated by some vertices $(u,h'),(v,h''),(w,h''')\in D$, where $h',h'',h'''\in N_H(h)$. By (R) these vertices are projected to $h',h'',h'''$, respectively, in one of the copies $H_1,H_2$ or $H_3$ (more precisely, $(u,h')$ in $H_1$ or $H_2$, $(v,h'')$ in $H_1$ or $H_3$ and $(w,h''')$ in $H_2$ or $H_3$). It is easy to see that in at most one of the copies $H_1,H_2,H_3$ the vertex $h$ is not vertically dominated after these three projections are performed. If $H_i$, $i\in \{1,2,3\}$, is such a copy, we let $(x,h)$ project to $h$ in $H_i$, otherwise $(x,h)$ is projected in an arbitrary copy of $H$. \smallskip {\bf Case $3/2$.} Again assume without loss of generality that $\{1,h\},\{2,h\}$ and $\{3,h\}$ are vertically undominated, and let $(x,h),(y,h)\in D$. Since $\{x,y\}$ is not a dominating set of $G$, there exists a vertex $(z,h)\in G^h$ that is not adjacent to these two vertices. Moreover, $z\not \in Q$, and $(z,h)$ is vertically dominated by some vertex $(z,h')\in D$, where $h'\in N_H(h)$. The projection of $(z,h')$ to the copy of $h'$ in some $H_i$, dominates the copy of $h$ in $H_i$. For the other two copies of $h$ we use projection of $(x,h),(y,h)$ to $h$ in these copies. Note that such projections can be done, by obeying rule (R), because each of the vertices $x$ and $y$ is adjacent to at least two vertices from $I$ and $\{x,y\}$ dominates $I$. \smallskip {\bf Case $3/3$.} Let $\{1,h\},\{2,h\}$ and $\{3,h\}$ be vertically undominated, and let $(x_1,h),(x_2,h)$ and $(x_3,h)$ be the vertices from $D$. For $i=1,2,3$, let $P_{S_i}$ be the set in which $x_i$ lies. Note that the sets $S_1,S_2,S_3$ enjoy Hall's condition, and so there exists a system of distinct representatives of these sets. That is, each set has a unique representative from $\{1,2,3\}$, say $S_i$ is represented by $\pi (i)$, where $\pi$ is the corresponding permutation. By projecting $(x_i,h)$ to $h$ in $H_{\pi(i)}$, the rule (R) is obeyed and for each $i\in [3]$ the copy of $h$ in $H_i$ is dominated by $h$ itself. \smallskip {\bf Case $2/1$.} Let $\{i,h\}$ and $\{j,h\}$ be vertically undominated, let $k$ be the unique index in $[3]\setminus \{i,j\}$, and let $(x,h)$ be the unique vertex in $((V(G)\setminus Q)\times \{h\})\cap D$. First assume that $|G^h\cap D|=1$. Clearly, the vertex $(x,h)$ then dominates $(Q_i\cup Q_j)\times \{h\}$. Since $\{x,v_k\}$ is not a dominating set of $G$ (as $\gamma(G)=3$), there exists a vertex $(z,h)\in P_{\{i,j\}}$, which is not adjacent to $(x,h)$. Thus $(z,h)$ must be vertically dominated, i.e. there exists $h'\in N_H(h)$ such that $(z,h')\in D$. By the rule (R), $(z,h')$ is projected to $h'$ in $H_i$ or in $H_j$, and so the copy of the vertex $h$ is dominated by $h'$ either in $H_i$ or in $H_j$; we may assume without loss of generality that the copy of $h$ in $H_i$ is dominated by $h'\in D_i$. Since $x$ is adjacent to $v_j$, we can project $(x,h)$ to the copy of $h$ in $H_j$, by which (R) is obeyed, and so all three copies of $h$ are dominated. Next, if $|G^h\cap D|\ge 3$, this readily implies that $|(Q_k\times \{h\}) \cap D|\ge 2$. Since in the first step the (at least two) vertices from $Q_k\times \{h\}$ project to the same vertex $h$ in $H_k$, at least one of these vertices is free. We project it to $h$ in $H_i$, and project $(x,h)$ to $h$ in $H_j$, making all three copies of $h$ dominated. In the remainder of this case, we can assume that $|G^h\cap D|=2$. Now, suppose that $(v_k,h)\in D$. Since $x\in V(G)\setminus Q$, it is either in $P_{i,j}$ or $(x,h)$ is a free vertex, but in any case, $(x,h)$ can be projected to any copy of $h$, without violating (R). We proceed analogously as in the case $|G^h\cap D|=1$. Notably, since $\{x,v_k\}$ is not a dominating set of $G$, there exists a vertex $(z,h)\in P_{\{i,j\}}$, which is not adjacent to $(x,h)$. Thus there exists $h'\in N_H(h)$ such that $(z,h')\in D$. By (R), $(z,h')$ is projected to $h'$ in $H_i$ or in $H_j$, and so the copy of the vertex $h$ is dominated by $h'$ either in $H_i$ or in $H_j$; we project $(x,h)$ to the other copy of $h$, and so all three copies of $h$ are dominated. Finally, let $(v,h)\in D$, where $v\in P_k$, be the only vertex in $D\cap G^v$ beside $(x,h)$. At this point we assume that the first and the second step of projections to the copies of $H$ have already been performed for all vertices of $D$ in all $G$-fibers in which this was possible. That is, for all $G^h$, which fall under any of the above cases (including the preceding subcases of Case $2/1$), the projections of the second step were also performed. The projections can be done in any order; by starting in an arbitrary $G$-fiber $G^h$ and project its vertices of $((V(G)\setminus Q)\times \{h\})\cap D$ according to the rule (R), which in turn determines the projections of the neighboring $G$-fibers, and so on. The only eventual remaining $G$-fibers are the ones that fall under the subcase of Case $2/1$, in which we are now, and which will be described in what follows. Suppose that there is a neighboring $G$-fiber $G^{h'}$ of $G^h$, in which the projections of the second step have also not been performed yet. This means that $G^{h'}$, where $h'\in N_H(h)$, also falls under the last subcase of Case $2/1$. This implies that there exists a vertex $(x',h')$, which is unique in $((V(G)\setminus Q)\times \{h\})\cap D$, and there is only one other vertex of $D\cap G^{h'}$. Now, since $\{i,h\}$ and $\{j,h\}$ are vertically undominated, this implies that the remaining vertex of $D\cap G^{h'}$ lies in $Q_k\times \{h'\}$. Hence, we find that $(x',h')$ can be projected to $h'$ in any copy of $H$ (in the same way, as we deduced it for $(x,h)$). We project $(x,h)$ to $h$ in $H_i$ and $(x',h')$ to $h'$ in $H_j$, by which each of $h$ and $h'$ are dominated in all three copies of $H$. More generally, we can clearly resolve the projections in the second step for any nontrivial connected subgraph $\tilde{H}$ of $H$, where $G^h$ falls under this subcase of Case $2/1$ for all $h\in \tilde{H}$. The final remaining case is that the mentioned subgraph is trivial, i.e. for all the neighboring $G$-fibers of $G^h$ the projections fall under previous cases of the second step (which have already been performed). Suppose that there is a $G$-fiber $G^{h'}$, where $h'\in N_H(h)$, such that a vertex $(u,h')\in D$ is projected in the second step to $h$ in $H_i$ (or $H_j$ resp.). Then we can clearly conclude the proof of this case, by projecting $(x,h)$ to $h$ in $H_j$ (or $H_i$ resp.), and so all copies of $h$ are dominated. Hence, we may assume that for each $h'\in N_H(h)$, the vertices from $((V(G)\setminus Q)\times \{h\})\cap D$ are projected to $h'$ in $H_k$. If this is the case, then we arrive at the {\bf third step}. In the third step we make a nonstandard re-projection, by declaring that $(v,h)$ is projected to one of $H_i$ or $H_j$ instead of $H_k$ (that is, we delete $h$ from $D_k$ and put it in $D_i$ or $D_j$). At the same time we project $(x,h)$ to $h$ in $H_j$ (or $H_i$ resp., taking care that (R) is obeyed), by which $h$ is dominated in the copies $H_i$ and $H_j$. We claim that by this re-projection $h$ remains dominated also in the copy $H_k$, and that all neighbors $h'\in N_{H_k}(h)$ remain dominated. That is, we claim that $h\in D_k$ is not needed in the constructed dominating set of $H_k$; i.e. it remains a dominating set of $H_k$ also after we remove $h$ from it. Since $\{x,v\}$ is not a dominating set of $G$, there exists a vertex $y\in V(G)$, which is not dominated by these two vertices. Note that $y\in P_k\cup (V(G)\setminus Q)$. Now, this implies that $(y,h)$ must be vertically dominated, i.e. there exists $(y,\overline{h})\in D$, where $\overline{h}\in N_H(h)$. In any case ($y$ being either in $P_k$ or in $V(G)\setminus Q$), the vertex $(y,\overline{h})$ is projected to $\overline{h}$ in $H_k$. Thus $h$ is dominated by $\overline{h}\in D_k$. Suppose that there is a vertex $h'\in N_{H}(h)$ such that $h'\in V(H_k)$ was dominated only by $h$ before the third step. In particular, this implies that $(v_k,h')$ is not vertically dominated. Since $(v_j,h')$ and $(v_i,h')$ are not in $D$ (because $\{i,h\}$ and $\{j,h\}$ are vertically undominated), we infer that $(v_k,h')$ is dominated by a vertex $(y,h')\in D$, where $y$ is in $V(G)\setminus Q$. Since $(y,h')$ is projected in the second step to $h'$ in $H_k$ we derive a contradiction with the assumption that $h'\in V(H_k)$ was not dominated by $D_k\setminus \{h\}$ after the first two steps. This contradiction implies that after the re-projection of $h$ from $D_k$ to $D_i$ or $D_j$, the set $D_k\setminus\{h\}$ remains a dominating set of $H_k$, and so the proof is complete. \bigskip %Although we see no immediate way of how to generalize this proof to bigger $\gamma(G)$, we think that the approach is more transparent %as in the previous proof of this result, and it may well lead to improvements and generalizations. \begin{thebibliography}{99} \bibitem{alla-78} R.~B.~Allan, R.~Laskar, On domination and independent domination numbers of a graph, Discrete Math. 23 (1978) 73--76. \bibitem{bg-1979} A.~M. Barcalkin, L.~F. German, The external stability number of the {C}artesian product of graphs, Bul. Akad. Stiinte RSS Moldoven. 94 (1979) 5--8. \bibitem{brdo-2012} B.~Bre{\v{s}}ar, P.~Dorbec, W.~Goddard, B.~L.~Hartnell, M.~A.~Henning, S.~Klav{\v{z}}ar, D.~F.~Rall, Vizing's conjecture: a survey and recent results, J. Graph Theory 69 (2012) 46--76. \bibitem{bhr-2008} B.~Bre{\v{s}}ar, M.~A. Henning, D.~F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008) 213--225. \bibitem{imagination} B.~Bre\v sar, S.~Klav\v zar, D.F.~Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010) 979--991. \bibitem{cs-2000} W.~E. Clark, S.~Suen, An inequality related to {V}izing's conjecture, Electron. J. Combin. 7 (2000), \#N4, 3 pp. \bibitem{gy-2015} I.~Gonz\'{a}lez Yero, Partial product of graphs and Vizing's conjecture, Ars Math. Contemp. 9 (2015) 19--25. \bibitem{HaImKl} R. Hammack, W. Imrich and S. Klav\v{z}ar, \emph{Handbook of Product Graphs, Second Edition}, CRC Press, Boca Raton, FL, 2011. \bibitem{hr-1998} B.~Hartnell, D.~F. Rall, Domination in {C}artesian products: {V}izing's conjecture, In {\em Domination in graphs}, volume 209 of {\em Monogr. Textbooks Pure Appl. Math.}, pages 163--189, Dekker, New York, 1998. \bibitem{imklra-2008} W.~Imrich, S.~Klav\v zar, D.~F.~Rall, {\em Topics in Graph Theory: Graphs and Their Cartesian Product}, A K Peters, Wellesley, MA, 2008. \bibitem{st-2012} S.~Suen, J.~Tarr, An improved inequality related to Vizing's conjecture, Electron. J. Combin. 19(1) (2012), \#P8. \bibitem{S2004} L.~Sun, A result on Vizing's conjecture, Discrete Math. 275 (2004) 363--366. \bibitem{V1963} V.~G. Vizing, The cartesian product of graphs, Vy\v cisl. Sistemy 9 (1963) 30--43. \bibitem{wu-2013} Y.~Wu, An improvement on Vizing's conjecture, Inf. Process. Lett. 113 (2013) 87--88. \end{thebibliography} \end{document}