# Experiments on intense ion beam formation with inhomogeneous electric field

S. S. Vybin, V. A. Skalyga, I. V. Izotov, S. V. Golubev, S. V. Razin, R. A.
Shaposhnikov, M. Yu. Kazakov, A. F. Bokhanov, S. P. Shlepnev  Institute of
Applied Physics of Russian Academy of Sciences, 46 Ulyanov Str., 603950,
Nizhny Novgorod, Russia<EMAIL_ADDRESS>
###### Abstract

We report on a successful test of a new method for intense ion beam formation
using an extraction with inhomogeneous electric field. Its key feature is a
special shape of the extraction electrodes providing a higher rate of ion
acceleration. It is applicable to any ion source type and could be used to
improve performance of a wide range of plasma devices. The proof of concept
was carried out using a high-current electron-cyclotron resonance ion source
SMIS 37. High efficiency of the new extraction and proton beam formation with
a record current density of up to $1.1~{}\text{A}~{}\text{cm}^{-2}$ was
demonstrated.

Keywords: Extraction system design, High current ion beam, Proton beam, Ion
source

##  1 Introduction

The difficulties in the high-quality and high-intensity ion beams formation
are due to the significant space charge, which is the most influential at the
initial stage of acceleration, when the ion energy is still low. In [1] the
authors of this article proposed and numerically substantiated the original
approach to a significant expansion of the possibilities for the formation of
ion beams, associated with the use of shaped electrodes that provide a highly
nonuniform distribution of the electric field in the interelectrode gap. The
shape of the electrodes is chosen to achieve the major drop in the
accelerating potential being located close to the plasma electrode, thereby
increasing the rate of particle acceleration in the region most sensitive to
self-action (the region with a low ion velocity, thus, high space charge). A
feature of the proposed system is that it increases the electric field only in
the area where it is necessary (in contrast to traditional systems in which
the field increases throughout the accelerating gap).

The new approach of the extraction system design was proposed in [1]. It is
applicable to every ion beam source, no matter of its type. This work shows an
example of the new geometry usage at a particular ion beam source - SMIS 37.
The experiment is carried out to prove the concept and confirm conclusions
which are made in [1].

The considered system with inhomogeneity of the electric field is shown in
Fig. 1a. The increase of the puller hole diameter does not significantly
affect the ion beam formation, but it reduces the ion flux on the puller and
improves the extraction system reliability. For comparison, the flat extractor
is also shown in the figure. A significant increase in the electric field is
achieved in the new geometry at the same voltage. This is illustrated with
colormaps of the electric field modulus (a, b), and graphs of the electric
field distributions on the system axis (c).

Figure 1:  The comparison of the flat extractor and the system with
inhomogeneity of the electric field. The interelectrode distances
($d_{1}=d_{2}$) and bias voltages are equal. The significant increase of the
electric field modulus near the plasma electrode tip is demonstrated with
colormaps (a, b) and distribution on the system axis (c).  Figure 2:  The SMIS
37 facility scheme.

The use of the extraction system with highly inhomogeneous distribution of the
electric field will make it possible to achieve significant progress in the
characteristics of the generated ion beams. It allows for either an increase
in the current density of the extracted beam at a constant accelerating
voltage, or a decrease in the optimal extraction voltage in the case when the
current density is determined by the plasma emissivity. An additional
advantage of the new geometry is its weak sensitivity to the interelectrode
distance, which makes it possible to effectively solve technical and
engineering problems common for ion optics, in particular, those related to
the electric breakdown resistance of the accelerating gap [1].

Improvement of the ion beam formation system makes it possible to achieve
substantial progress in challenges, where the existing ion sources are not
efficient enough. First, the increase of the total ion beam current without
losses in its quality is feasible when the ion source with extra emission
ability is used as an injector for modern accelerators. Second, the effective
formation of a low energy ion beam is required for ion implantation [2].
Third, the use of the new approach can be especially beneficial for the
formation of focused ion beams (FIBs), since it allows one to significantly
exceed the limitations on the current density associated with the Child-
Langmuir law in the planar case. Ion sources for FIB are characterized by
small apertures of electrodes in comparison with interelectrode distances [3].
Decrease in the interelectrode distance is limited by the electrical breakdown
of the interelectrode gap and by technological difficulties (accuracy of
positioning the electrodes). This aspect ratio is far from optimal in the case
of the flat geometry, and the use of the proposed geometry greatly simplifies
the solution of the problem.

It should be noted that the new approach to the formation of an ion beam is
also applicable to a multicomponent plasma. In particular, when forming a beam
of negative ions, it is possible to decrease the power of the co-extracted
electron beam [4]. The use of the new approach makes it possible to unleash
the potential of those facilities, where the plasma emission ability exceeds
the capability of the extraction system [5].

This article is devoted to the experimental verification of the proposals
formed in [1]. The SMIS 37 [5] pulsed facility was chosen as an experimental
base. It is a high-current ion source based on plasma of an electron cyclotron
resonance (ECR) discharge, sustained by the radiation of a gyrotron with a
frequency of $37.5~{}\text{GHz}$ and a power of up to $100~{}\text{kW}$ in a
magnetic trap of a simple mirror configuration. The combination of high
frequency and high microwave power allows for the formation of dense plasma
fluxes (ion flux up to $10~{}\text{A}~{}\text{cm}^{-2}$) through the magnetic
trap plugs, which are used to obtain ion beams with record brightness for ECR
ion sources.

SMIS 37 is a promising ion source with the so-called quasi-gas-dynamic plasma
confinement mode [6, 7], so-called a gas-dynamic ECR ion source [5]. To verify
the efficiency of the proposed approach, we compared the parameters of the
beams formed by the conventional flat-electrode extraction system with the
proposed one.

Earlier, SMIS 37 demonstrated the possibility of generating beams with unique
parameters: proton beams with a current of up to $500~{}\text{mA}$ at a
current density of $800~{}\text{mA}~{}\text{cm}^{-2}$, a fraction of atomic
ions of more than $95\%$, and a normalized rms emittance not exceeding
$0.1~{}\pi~{}\text{mm}~{}\text{mrad}$ [8]; beams of multiply charged nitrogen
and argon ions with current up to $200~{}\text{mA}$ and an average charge of
$4-5$ [9].

Despite the record level of previously obtained results, there are a number of
applications, which require the achievement of even higher currents (and
current densities) of ion beams, while keeping the emittance low. The
requirements of modern accelerators for light and multiply charged ion
injectors are constantly growing, and to meet those of projects such as ISIS
II [10] and HIAF [11] further enhancement of beam characteristics is needed.
The use of the new extraction system with strongly inhomogeneous electric
field distribution might be an important step towards the successful creation
of the required ion sources not only for the mentioned projects, but also for
many others, as well as make it possible to significantly improve the
performance of existing systems through an easy and low-cost upgrade.

##  2 Experimental facility

Figure 3:  The electrode photos and the extraction system cross sections for
the flat (a, b) and the “spherical” (c, d) geometry. The puller aperture in
the spherical case is several times larger than in the flat one.

The SMIS 37 facility scheme is shown in Fig. 2. Plasma is created using a
pulsed microwave gyrotron radiation at a frequency of $37.5~{}\text{GHz}$,
power up to $100~{}\text{kW}$ and a pulse duration of $1~{}\text{ms}$.
Microwave beam is coupled to the discharge chamber using an electrodynamic
system with an embedded gas feed line. Neutral gas is injected along the axis
of the plasma chamber. The chamber inner diameter is $38~{}\text{mm}$. A
simple magnetic trap with the mirror ratio of $R=5$ is used to create and
confine the plasma. The distance between the plugs is $250~{}\text{mm}$. The
magnetic field is created by the pulsed coils. The maximum magnetic field in
the plug reaches $4~{}\text{T}$. The resonant value of the magnetic field for
a frequency of $37.5~{}\text{GHz}$ is $1.34~{}\text{T}$. The pulse repetition
period is about $20~{}\text{s}$.

With hydrogen as a working gas, the plasma density reaches the level of
$2\cdot 10^{13}~{}\text{cm}^{-3}$, electron temperature - $50~{}\text{eV}$ and
ionization degree is close to $100\%$. This combination of temperature and
density provides a high density of the plasma flux from the trap and
corresponds to the quasi-gasdynamic confinement regime. The difference between
this regime when compared to the classical collision-less regime is that
electrons fill the loss cone in the velocity space due to the high frequency
of Coulomb scattering. The flux of electrons leaving the trap is limited by
the ion flux, the maximum velocity of which is equal to the ion-sound one
$V_{s}=\sqrt{T_{e}/M}$. The lifetime of electrons is determined by the mirror
ratio, ion-sound velocity and trap length: $\tau_{e}=LR/V_{s}$. Substituting
the typical values, one gets $\tau_{e}\sim 20~{}\mu\text{s}$. High plasma
density and short lifetime provides an ion current density in the plug of more
than $10~{}\text{A}~{}\text{cm}^{-2}$. To reduce the flux density to a level
acceptable for beam formation, the extraction system is moved from the plug to
the region of a weaker magnetic field. The distance from the plug of the
magnetic trap to the plasma electrode is $120~{}\text{mm}$. The value of the
magnetic field at the edge of the plasma electrode is about 10 times lower
than in the plug.

##  3 The beam extraction system

The two-electrode system for the ion beam formation, consisting of a plasma
electrode and a puller, was used. The maximum available extraction voltage on
the facility is $100~{}\text{kV}$. In the experiment, the current of the ion
beam passed through the formation system was measured using a Faraday cup
(FC), the size of which ensures the interception of the entire beam.

Single-aperture two-electrode extraction systems are characterized by three
parameters: the plasma electrode aperture $D_{1}$, the interelectrode distance
$L$, and the puller electrode aperture $D_{2}$.

The interelectrode distance is longer than plasma electrode and puller
apertures for the majority of flat extraction systems. These extractors suffer
from secondary electron emission in the case when the ion beam current density
is too high and the beam significantly diverges in the interelectrode region.
Therefore, the extraction system with significantly wider puller aperture was
used (see Fig. 3).

In [1] it was shown that the new approach allows for a significant increase in
$D_{2}$ without a noticeable decrease in the quality of beam formation, while
the flat extraction system efficiency suffers a lot from the increase in the
puller aperture. The diameter of the puller hole in the flat geometry in the
experiment was significantly smaller than in the new one (see Fig. 3). The
plasma electrode in the flat geometry has a considerable thickness (see Fig.
3b). This is necessary in order to ensure the same boundary conditions for the
plasma flow in the considered cases.

##  4 Experimental results

In the general case, the dependence of the beam current on the Faraday cup on
the extraction voltage $I_{FC}(U_{ext})$ has 2 regions with different modes of
beam formation. At low extraction voltages, a space charge limited mode is
realized, which is characterized by $I_{FC}\sim U_{ext}^{3/2}$ and corresponds
to the Child-Langmuir law. At higher voltages, the plasma-density-limited mode
(saturation mode) is realized, which is characterized by a constant current
value. An experimental comparison of the efficiency of the extraction systems
was made for two extraction systems with 3 mm and 5 mm plasma electrode
aperture. The experiments were carried out in modes with different plasma
emissivity.

###  4.1 Decrease of the optimal extraction voltage

Graphs of $I_{FC}(U_{ext})$ are shown for the 3 mm extraction hole case in
Fig. 4. In this case, the plasma emissivity was moderate, which made it
possible to achieve two extraction modes (firstly, the space charge limited
mode and then the plasma density limited mode) at available accelerating
voltages.

Figure 4:  The dependence of the Faraday cup current on the extraction
voltage. The plasma electrode aperture is 3 mm.

Figure 5:  The dependence of the Faraday cup (a) and puller (b) currents on
the extraction voltage. The plasma electrode aperture is 5 mm.

The use of the new ion beam formation system can significantly reduce the
optimal extraction voltage. Consider the point of intersection of the
approximation curves of the two extraction modes described above. For the flat
case, the voltage of the characteristic point is $22~{}\text{kV}$ and for the
new geometry - $10~{}\text{kV}$. Therefore, a significant decrease in the
optimal extraction voltage (by a factor of 2) is shown when using the new
geometry of electrodes.

###  4.2 Reduction of the puller current

In the following case the plasma emissivity was higher. For the flat case only
the space charge limited regime was achieved. Graphs of the Faraday cup and
puller currents dependencies on the extraction voltage are shown for the 5 mm
extraction hole case in Fig. 5. It is clearly seen that in this case the flat
system of electrodes did not allow for the utilization of the available plasma
flow, while the new system ensured the saturation of the extracted beam
current and its significantly higher value. The use of a tubular puller with a
large aperture in the new geometry made it possible not only to increase the
beam current, but also to significantly reduce the ion flux to the puller (see
Fig. 5b). This effect was predicted in [1] and it is a significant
technological advantage of the developed extraction system.

Figure 6:  The dependence of the Faraday cup and puller currents on the
extraction voltage for the new geometry in the maximum current density mode.
The plasma electrode aperture is 5 mm. Beam current waveforms in the points A
and B are shown in figure 7.

Let us compare the efficiency of the new geometry for the given
configurations. For this, we estimate the ratio of perveances $P$ of different
extraction systems. The following quantity is called perveance

$P=\frac{I_{beam}}{U_{ext}^{3/2}}.$

The value of perveance indicates how significant the space charge effect is on
the beam’s motion and is constant for the fixed geometry while operating in a
space-charge-limited mode. The value of the perveance ratio for the 3 mm
extraction hole case is $P_{new}/P_{old}=3.3$ and for the 5 mm case is
$P_{new}/P_{old}=2.3$.

The increase in perveance ratio, thus, the efficiency of the new extraction
system, becomes greater with the higher $L/D_{1}$ ratio. This fact confirms
the conclusions drawn in [1].

###  4.3 The record current density beam formation

Figure 7:  The Faraday cup current oscillograms at points A and B from figure
6.

The most significant experiment which proves the advantages of the proposed
extraction system with an inhomogeneous electric field distribution is the
demonstration of the possibility of the ion beam formation with a record
current density. The graph of $I_{FC}(U_{ext})$ is shown for the 5 mm
extraction hole case in Fig. 6.

Starting from a voltage of about $35~{}\text{kV}$, the current to the puller
reaches its minimum value. In this configuration, ion beams with currents from
$150~{}\text{mA}$ (which corresponds to an average current density of
$0.77~{}\text{A}~{}\text{cm}^{-2}$) at the extraction voltage of
$40~{}\text{kV}$ to $225~{}\text{mA}$ (which corresponds to an average current
density of $1.15~{}\text{A}~{}\text{cm}^{-2}$) at the voltage of
$53~{}\text{kV}$ were obtained. Waveforms of the beam current for points A, B
in Fig. 6 are shown in Fig. 7.

##  5 Conclusion

The new extraction system geometry makes it possible to overcome the
limitations on the ion beam current density, caused by the Child-Langmuir law
for flat geometry. The assumptions (theoretically substantiated in [1]) about
the effectiveness of using the new geometry of the electrodes for obtaining
high-current ion beams were successfully confirmed experimentally. It is shown
that under the same conditions the optimal voltage required for high-quality
beam formation using the system with inhomogeneity of the electric field is
reduced by a factor of two when compared to the flat geometry. This result
demonstrates the possibility of a significant increase in the beam current in
systems with a fixed extraction voltage with a sufficient emissivity of the
plasma. The relaxation of the requirements for the puller geometry not causing
the deterioration of the beam quality was clearly demonstrated. An increase in
the puller aperture, and even the use of the tubular puller, made it possible
to minimize the contact of the puller electrode with the ion beam, eliminate
secondary electrons emission from the puller and increase the electrical
breakdown resistance of the interelectrode gap. During the tests of the new
system, a proton beam with a record current density for any type of ECR ion
sources at the level of $1.15~{}\text{A}~{}\text{cm}^{-2}$ was obtained.
Experimental demonstration of the new extraction system efficiency makes it
possible to proceed to the next stages of its implementation at facilities of
various classes and purposes, sources of multiply charged ions, sources for
ion implantation, sources of negative ions, etc.

The work was supported by the project of the Russian Science Foundation Grant
No. 21-19-00844.

## References

## References

  * [1] S.S. Vybin, I.V. Izotov and V.A. Skalyga, High current ion beam formation with strongly inhomogeneous electrostatic field, Plasma Sources Sci. Technol., 29 11LT02 (2020)
  * [2] M. Sugitani, Ion implantation technology and ion sources, Rev. Sci. Instrum., 85, 02C315 (2014)
  * [3] J.V. Mathew and S. Bhattacharjeea, Compact electrostatic beam optics for multi-element focused ion beams: Simulation and experiments, Rev. Sci. Instrum., 82, 013501 (2011)
  * [4] D. Faircloth, O. Tarvainen, S. Lawrie, T. Sarmento, N. Savard, R. Abel, J. Macgregor, M. Whitehead, T. Wood, and C. Cahill, ISIS Penning Source Extraction Studies Reveal the 3-Dimensional Child–Langmuir Effect, Rev. Sci. Instrum., 91, 043307 (2020).
  * [5] V. A. Skalyga, S. V. Golubev, I. V. Izotov, R. L. Lapin, S. V. Razin, A. V. Sidorov, and R. A. Shaposhnikov, High-Current Pulsed ECR Ion Sources, Plasma Phys. Rep. 45, 984 (2019).
  * [6] V. Skalyga, V. Zorin, I. Izotov, S. Razin, A. Sidorov, and A. Bohanov, Gasdynamic ECR Source of Multicharged Ions Based on a Cusp Magnetic Trap, Plasma Sources Sci. Technol. 15, 727 (2006).
  * [7] S. Golubev, I. Izotov, S. Razin, A. Sidorov, V. Skalyga, A. Vodopyanov, V. Zorin, and A. Bokhanov, High Current ECR Source of Multicharged Ion Beams, Nucl. Instrum. Meth. B, 256, 537 (2007).
  * [8] V. Skalyga, I. Izotov, S. Razin, A. Sidorov, S. Golubev, T. Kalvas, H. Koivisto, and O. Tarvainen, High Current Proton Beams Production at Simple Mirror Ion Source 37, Rev. Sci. Instrum., 85, 02A702 (2014).
  * [9] V. Skalyga, I. Izotov, S. Golubev, A. Sidorov, S. Razin, A. Vodopyanov, O. Tarvainen, H. Koivisto, and T. Kalvas, New Progress of High Current Gasdynamic Ion Source (Invited), Rev. Sci. Instrum., 87, 02A716 (2016).
  * [10] J.-B. Lagrange, D. Adams, C. Brown, H. Cavanagh, I. Gardner, P. Griffin-Hicks, B. Jones, D. Kelliher, A. Letchford, S. Machida, J. Pasternak, B. Pine, J. Pozimski, C. Prior, G. Rees, C. Rogers, J. Thomason, C. Warsop, and R. Williamson, Progress on Design Studies for the ISIS II Upgrade, Proceedings of the 10th Int. Particle Accelerator Conf. IPAC2019, Australia (2019).
  * [11] J. C. Yang, J. W. Xia, G. Q. Xiao, H. S. Xu, H. W. Zhao, X. H. Zhou, X. W. Ma, Y. He, L. Z. Ma, D. Q. Gao, J. Meng, Z. Xu, R. S. Mao, W. Zhang, Y. Y. Wang, L. T. Sun, Y. J. Yuan, P. Yuan, W. L. Zhan, J. Shi, W. P. Chai, D. Y. Yin, P. Li, J. Li, L. J. Mao, J. Q. Zhang, and L. N. Sheng, High Intensity Heavy Ion Accelerator Facility (HIAF) in China, Nucl. Instrum. Meth. B, 317, 263 (2013).


1820163101277

# Partitioning the vertex set of $G$ to make $G\,\Box\,H$ an efficient open
domination graph

Tadeja Kraner Šumenjak1,2  Iztok Peterin2,3 Partially supported by the
Ministry of Science of Slovenia under the grant P1-0297. Douglas F. Rall4 This
author was supported by the grant “Internationalisation–a pillar of
development of University of Maribor.” and by a grant from the Simons
Foundation (#209654 to Douglas F. Rall). Aleksandra Tepeh3,5 This author was
partially supported by Slovenian research agency ARRS, program no. P1-00383,
project no. L1-4292, and Creative Core-FISNM-3330-13-500033.  University of
Maribor, FKBV, Hoče, Slovenia
IMFM, Ljubljana, Slovenia
University of Maribor, FEECS, Maribor, Slovenia
Furman University, Greenville, SC, USA
Faculty of Information Studies, Novo Mesto, Slovenia

(2015-8-18; 2016-5-26; 2016-5-31)

###### Abstract

A graph is an efficient open domination graph if there exists a subset of
vertices whose open neighborhoods partition its vertex set. We characterize
those graphs $G$ for which the Cartesian product $G\,\Box\,H$ is an efficient
open domination graph when $H$ is a complete graph of order at least 3 or a
complete bipartite graph. The characterization is based on the existence of a
certain type of weak partition of $V(G)$. For the class of trees when $H$ is
complete of order at least 3, the characterization is constructive. In
addition, a special type of efficient open domination graph is characterized
among Cartesian products $G\,\Box\,H$ when $H$ is a $5$-cycle or a $4$-cycle.

###### keywords:

efficient open domination, Cartesian product, vertex labeling, total
domination

##  1 Introduction

The domination number of a graph $G$ is a classical invariant in graph theory.
It is the minimum cardinality of a set $S$ of vertices for which the union of
the closed neighborhoods centered in vertices of $S$ is the entire vertex set
of $G$. Hence, each vertex of $G$ is either in $S$ or is adjacent to a vertex
in $S$. In other words, we can say that vertices of $S$ control each vertex
outside of $S$. A classical question in such a situation is: who controls the
vertices of $S$? One possible solution to this dilemma is total domination. A
set $D\subseteq V(G)$ is a total dominating set of $G$ if every vertex of $G$
is adjacent to a vertex of $D$. (Hence, vertices of $D$ are also controlled by
$D$.)

A natural question for a graph $G$ is whether we can find a total dominating
set $D$ such that the union of the open neighborhoods of the vertices in $D$
is $V(G)$ but so that these open neighborhoods also form a partition of
$V(G)$. The concept has been presented under the names total perfect codes
Cockayne et al. (1993), efficient open domination Gavlas and Schultz (2002)
and exact transversals Cowen et al. (2007). In the present work we follow the
terminology of efficient open domination, and we say that a graph $G$ is an
efficient open domination graph if $G$ has a total dominating set $D$ such
that the open neighborhoods of the vertices of $D$ form a partition of $V(G)$.
A similar concept for ordinary domination was first investigated by Biggs
(1973) and Kratochvíl (1986). They call a graph 1-perfect if it contains a
perfect code, that is, a set of vertices whose closed neighborhoods partition
the vertex set.

The problem of establishing whether a graph $G$ is an efficient open
domination graph is an $NP$-complete problem; see Gavlas et al. (2003); McRae
(1984). Gavlas et al. (2003) gave a recursive characterization of the class of
efficient open domination trees. Gavlas and Schultz (2002) presented various
properties of efficient open domination graphs. The efficient open domination
graphs that are also Cayley graphs were studied by Tamizh Chelvam and
Mutharasu (2012) and efficient open domination grid graphs by Cowen et al.
(2007); Dejter (2008); Klostermeyer and Goldwasser (2006). Moreover, Abay-
Asmerom et al. (2008) characterized those direct product graphs that are
efficient open domination graphs.

Several graph products have been investigated in the last few decades and a
rich theory involving the structure and recognition of classes of these graphs
has emerged Hammack et al. (2012). The most studied graph products are the
Cartesian, strong, direct, and lexicographic. These four are also called the
_standard products_. One approach to graph products is to deduce properties of
a product with respect to (the same) properties of its factors. See a short
collection of these types involving total domination and perfect codes in
Dorbec et al. (2006); Gravier (2002); Henning and Rall (2005); Ho (2008);
Jerebic et al. (2005); Klavžar et al. (2006); Kuziak et al. (2014a, b); Mekiš
(2010); Rall (2005). The domination related questions on the Cartesian product
seems to be the most problematic among the standard products. We just mention
Vizing’s conjecture, which says that the domination number of a Cartesian
product is at least the product of the domination numbers of the two factors.
Settling this conjecture is one of the most challenging problems in the area
of domination (see the recent survey on Vizing’s conjecture Brešar et al.
(2012)). Efficient open domination is no exception, which could be the reason
it has not been studied intensively yet in the Cartesian product setting.
Other than the results on grid graphs mentioned above, a step forward in this
direction was made only recently by Kuziak et al. (2014b) where some special
types of Cartesian products were considered. In the same paper complete
descriptions of efficient open domination graphs among lexicographic and
strong products of graph were given.

The aim of this paper is to show how the problem of finding efficient open
domination graphs among Cartesian products can be approached by partitioning
the vertex set of one factor. In the next section we set the context by
supplying needed definitions and previous results in this area. In Section 3
we prove that for $r\geq 3$, the graph $G\,\Box\,K_{r}$ has an efficient open
dominating set if and only if $V(G)$ has a weak partition that satisfies
certain properties. This provides a way to construct graphs with efficient
open dominating sets in this family of Cartesian products. In addition we give
a structural characterization of the trees $T$ such that $T\,\Box\,K_{r}$ has
an efficient open dominating set. Section 4 addresses this weak partition
approach to graphs of diameter 2.

##  2 Definitions and previous results

Throughout the article we consider only finite, simple graphs. For most common
graph theory notation and definitions we follow the book by Hammack et al.
(2012). In particular, our definitions and notation for open ($N(v)$) and
closed ($N[v]$) neighborhoods of a vertex $v$, for distance ($d_{G}(u,v)$)
between a pair of vertices and for the diameter ($\mathrm{diam}(G)$) of a
graph are the same as theirs. The distance $d_{G}(e,v)$ between an edge $e$
and a vertex $v$ in $G$ is the shortest distance between $v$ and the two end
vertices of $e$, while the distance $d_{G}(e_{1},e_{2})$ between edges $e_{1}$
and $e_{2}$ is the shortest distance between the end vertices of $e_{1}$ and
the end vertices of $e_{2}$. In general, for nonempty subsets $P$ and $Q$ of
$V(G)$, the distance $d_{G}(P,Q)$ between them is the shortest distance
between a vertex from $P$ and a vertex from $Q$. A _weak partition_ of a set
$X$ is a collection of pairwise disjoint subsets of $X$ whose union is $X$. We
emphasize that, in contrast to a partition, members of a weak partition are
allowed to be empty. The subgraph induced by a subset $S$ of $V(G)$ is denoted
by $\left\langle S\right\rangle$. A _matching_ in $G$ is any (possibly empty)
set of independent edges. If $r$ is a positive integer, then the vertex set of
each of the graphs $P_{r}$, $K_{r}$, and $C_{r}$ (if $r>2$) will be the
interval $[r]$ defined by $[r]=\\{1,\ldots,r\\}$.

Since this present work concerns total domination on Cartesian products, we
include several of the important definitions here for the sake of
completeness. We say that a vertex $x$ of $G$ _dominates_ a vertex $y$
(equivalently, $y$ _is dominated by_ $x$) if $y\in N(x)$. A subset $D$ of
$V(G)$ is a _total dominating set_ of $G$ if each vertex in $G$ is dominated
by at least one vertex in $D$. The _total domination number_ of a graph $G$ is
the minimum cardinality of a total dominating set of $G$ and is denoted by
$\gamma_{t}(G)$. The _Cartesian product_ , $G\,\Box\,H$, of graphs $G$ and $H$
is a graph with $V(G\,\Box\,H)=V(G)\times V(H)$. Two vertices $(g,h)$ and
$(g^{\prime},h^{\prime})$ are adjacent in $G\,\Box\,H$ whenever
($gg^{\prime}\in E(G)$ and $h=h^{\prime}$) or ($g=g^{\prime}$ and
$hh^{\prime}\in E(H)$). For a fixed $h\in V(H)$ we call $G^{h}=\\{(g,h)\in
V(G\,\Box\,H):g\in V(G)\\}$ a $G$-_layer_ in $G\,\Box\,H$. Similarly, an
$H$-_layer_ ${}^{g}\\!H$ for a fixed $g\in V(G)$ is defined as
${}^{g}\\!H=\\{(g,h)\in V(G\,\Box\,H):h\in V(H)\\}$. Notice that the subgraph
of $G\,\Box\,H$ induced by a $G$-layer or an $H$-layer is isomorphic to $G$ or
$H$, respectively. The map $p_{G}:V(G\,\Box\,H)\rightarrow V(G)$ defined by
$p_{G}((g,h))=g$ is called a _projection map onto_ $G$. Similarly, we define
$p_{H}$ as the _projection map onto_ $H$. Projections are defined as maps
between vertices, but frequently it is more useful to see them as maps between
graphs.

A graph $G$ is an _efficient open domination graph_ (shortly an _EOD-graph_)
if there exists a set $D$, called an _efficient open dominating set_ (shortly
an _EOD-set_), for which $\bigcup_{v\in D}N(v)=V(G)$ and $N(u)\cap
N(v)=\emptyset$ for every pair $u$ and $v$ of distinct vertices of $D$. Note
that two different vertices of an EOD-set are either adjacent or at distance
at least three. It is easy to see that the path $P_{n}$ is an EOD-graph if and
only if $n\not\equiv 1\pmod{4}$, while the cycle $C_{n}$ is an EOD-graph if
and only if $n\equiv 0\pmod{4}$. Let $G$ and $H$ be graphs such that
$G\,\Box\,H$ is an EOD-graph with an EOD-set $D$. Note that the projection of
an edge in $\left\langle D\right\rangle$ onto $G$ is either a vertex or an
edge. When the projection of every edge in $\left\langle D\right\rangle$ onto
$G$ is an edge, we say that $D$ is a _parallel EOD-set_ with respect to $G$. A
Cartesian product that contains a parallel EOD-set with respect to one of its
factors is called a _parallel EOD-graph_.

Among the class of nontrivial Cartesian products several infinite families of
EOD-graphs have been found. In Cowen et al. (2007); Klostermeyer and
Goldwasser (2006) the authors investigated EOD-graphs among the grid graphs
(that is, Cartesian products of paths). Results from both papers are merged in
the following characterization.

###### Theorem 2.1

_Cowen et al. (2007); Klostermeyer and Goldwasser (2006)_ Let $t\geq r\geq 3$.
The grid graph $P_{r}\,\Box\,P_{t}$ is an EOD-graph if and only if $r$ is an
even number and $t\equiv x\pmod{r+1}$ for some $x\in\\{1,r-2,r\\}$.

Some partial results on EOD-graphs in the family of torus graphs (Cartesian
products of cycles) were presented by Dejter (2008), by characterizing only
those with a parallel EOD-set (there referred to as a parallel total perfect
code).

###### Theorem 2.2

_Dejter (2008)_ The Cartesian product $C_{r}\,\Box\,C_{t}$ has a parallel EOD-
set if and only if $r$ and $t$ are multiples of four.

Kuziak et al. (2014b) recently continued with the study of EOD-graphs among
tori and cylinders (Cartesian product of a path and a cycle).

###### Proposition 2.3

_Kuziak et al. (2014b)_ Let $t\geq 4$. The torus $C_{4}\,\Box\,C_{t}$ is an
EOD-graph if and only if $t\equiv 0\pmod{4}$.

In addition, they proved that $C_{r}\,\Box\,C_{t}$ is not an EOD-graph if
$r\in\\{3,5,6,7\\}$ and $t\geq r$. Based on the above observations they posed
the following conjecture.

###### Conjecture 2.4

_Kuziak et al. (2014b)_ Let $r$ and $t$ be integers such that $r\geq 3$ and
$t\geq 3$. The torus $C_{r}\,\Box\,C_{t}$ is an EOD-graph if and only if
$r\equiv 0\pmod{4}$ and $t\equiv 0\pmod{4}$.

The same authors characterized the graphs $G$ for which $G\,\Box\,K_{2}$ is an
EOD-graph. In order to do this they introduced the so-called zig-zag graphs,
Kuziak et al. (2014b). Let $G$ be a graph on at least three vertices and
$E^{\prime}=\\{e_{1},\ldots,e_{k}\\}$ a subset of $E(G)$, where
$e_{i}=u_{i}v_{i}$ for every $i\in[k]$, with the following properties:

  * $(i)$

$N(u_{i})\cap N(v_{i})=\emptyset$;

  * $(ii)$

$d_{G}(e_{i},e_{j})\geq 2$ for $1\leq i<j\leq k$;

  * $(iii)$

for every $x\in V(G)-\\{u_{i},v_{i}:i\in[k]\\}$ there exist unique $j$ and
$\ell$, $j\neq\ell$, such that $d_{G}(x,e_{j})=d_{G}(x,e_{\ell})=1$;

  * $(iv)$

for every sequence $e_{i_{1}},\ldots,e_{i_{j}}$ of distinct edges with $j>2$
and with
$d_{G}(e_{i_{{}_{\ell}}},e_{i_{{}_{\ell+1\pmod{j}}}})=2$ for
$\ell\in\\{1,\ldots,j\\}$, $j$ must be an even number.

We call $E^{\prime}$ a _zig-zag set_ of $G$ and, if there exists a zig-zag set
in $G$, we call $G$ a _zig-zag graph_.

###### Theorem 2.5

_Kuziak et al. (2014b)_ If $G$ is a zig-zag graph, then $G\,\Box\,K_{2}$ is an
EOD-graph.

Not all EOD-graphs among $G\,\Box\,K_{2}$ are given by the above theorem.
Kuziak et al. observed that for a description of all EOD-graphs among
Cartesian products of graphs with $K_{2}$, a certain combination of zig-zag
graphs and 1-perfect graphs is needed (see Kuziak et al. (2014b) for details).

One can observe that for $r>2$, every EOD-set in $G\,\Box\,K_{r}$ is a
parallel EOD-set with respect to $G$. Namely, if an edge induced by two
vertices of a vertex subset $A$ of $G\,\Box\,K_{r}$ projects to a single
vertex $g\in V(G)$, then the layer ${}^{g}\\!K_{r}$ contains a vertex that is
dominated more than once by $A$. This observation led to the idea of how to
approach the problem of finding EOD-graphs among $G\,\Box\,K_{r}$ for $r>2$.
This is presented in the next section.

##  3 $G\,\Box\,K_{r}$ for $r>2$

In order to obtain a characterization of EOD-graphs among $G\,\Box\,K_{r}$,
$r>2$, we introduce a new concept, based on a weak partition of the vertex set
of $G$. As we will see in later sections, a modification of this concept can
be used for the construction of EOD-graphs that are Cartesian products
$G\,\Box\,H$ where $H$ belongs to several other special classes of graphs.

Let $r$ be an integer larger than 1. We call a graph $G$ a _$K_{r}$ -amenable
graph_ if there exists a weak partition $\\{V_{0},V_{1},\ldots,V_{r}\\}$ of
$V(G)$, such that

  * (A)

if $x\in V_{0}$, then $|N(x)\cap V_{i}|=1$ for every $i\in[r]$,

  * (B)

$\left\langle V_{i}\right\rangle$ is a matching in $G$ for every $i\in[r]$,

  * (C)

$\left\langle V_{1}\cup\cdots\cup V_{r}\right\rangle$ is a matching in $G$.

For the sake of clarity in the above definition we emphasize that the induced
subgraphs $\left\langle V_{i}\right\rangle$ and $\left\langle
V_{1}\cup\cdots\cup V_{r}\right\rangle$ do not contain any edges other than
those in their perfect matchings.

We first prove that $K_{2}$-amenable graphs do not differ from zig-zag graphs.

###### Theorem 3.1

A graph $G$ is a $K_{2}$-amenable graph if and only if $G$ is a zig-zag graph.

######  Proof 3.2.

Let $G$ be a $K_{2}$-amenable graph with a weak partition
$\\{V_{0},V_{1},V_{2}\\}$ of $V(G)$ that satisfies conditions (A), (B) and
(C). We will show that $E^{\prime}=\left\langle V_{1}\cup V_{2}\right\rangle$
is a zig-zag set of $G$ by demonstrating that conditions $(i)-(iv)$ hold.
Since $\left\langle V_{1}\cup V_{2}\right\rangle$, $\left\langle
V_{1}\right\rangle$ and $\left\langle V_{2}\right\rangle$ are matchings,
$E^{\prime}$ is a set of edges $\\{e_{1},\ldots,e_{k}\\}$. By the same
argument we derive that $d_{G}(e_{i},e_{j})\geq 2$ for $i\neq j$, and thus
$(ii)$ holds. Let $e_{i}=u_{i}v_{i}$ for every $i\in[k]$. If $x\in
N(u_{i})\cap N(v_{i})$ for some $i\in[k]$, then $x\in V_{0}$ by the matching
argument again. But this contradicts condition (A) since $|N(x)\cap V_{i}|\geq
2$ in this case. Hence $(i)$ also holds. If $x\in
V(G)-\\{u_{i},v_{i}:i\in[k]\\}$, then $x\in V_{0}$. By (A) we have that
$|N(x)\cap V_{i}|=1$ for every $i\in\\{1,2\\}$, which implies the existence of
exactly two different edges $e_{j}$ and $e_{\ell}$ of $E^{\prime}$ with
$d_{G}(x,e_{j})=d_{G}(x,e_{\ell})=1$. This proves $(iii)$. To prove $(iv)$,
let $e_{i_{1}},e_{i_{2}},\ldots,e_{i_{j}}$, $j>2$, be a sequence of distinct
edges with $d_{G}(e_{i_{{}_{\ell}}},e_{i_{{}_{\ell+1\pmod{j}}}})=2$ for
$\ell\in[j]$. In addition, let $x_{\ell}$ be a common neighbor of
$e_{i_{{}_{\ell}}}$ and $e_{i_{{}_{\ell+1\pmod{j}}}}$. As before, $x_{\ell}\in
V_{0}$ for every $\ell\in[j]$. Without loss of generality, suppose the end-
vertices of the edge $e_{i_{1}}$ belong to $V_{1}$. By condition (A) for the
vertex $x_{1}$, the end-vertices of $e_{i_{2}}$ belong to $V_{2}$. The same
argument for the vertex $x_{2}$ implies that the end-vertices of $e_{i_{3}}$
belong to $V_{1}$. Continuing this way, we get a zig-zag pattern for the end-
vertices of $e_{i_{1}},e_{i_{2}},\ldots,e_{i_{j}}$. If $j$ is an odd number,
then the end-vertices of $e_{i_{1}}$ and $e_{i_{j}}$ are both in $V_{1}$,
which gives a contradiction with condition (A) for the vertex $x_{j}$. Thus
$j$ is an even number and $(iv)$ holds as well.

Now let $G$ be a zig-zag graph with a zig-zag set
$E^{\prime}=\\{e_{1},\ldots,e_{k}\\}$ where $e_{i}=u_{i}v_{i}$. We set
$V_{0}=V(G)-\\{u_{i},v_{i}:i\in[k]\\}$. Observe that $E^{\prime}$ can be
partitioned as $E^{\prime}=E_{1}\cup\cdots\cup E_{t}$ such that for each
$i\in[t]$, the following holds. The set $E_{i}$ is a maximal set of edges such
that between any two distinct edges $e_{j}$ and $e_{n}$ from $E_{i}$ there
exists a sequence $e_{j}=e_{j_{0}},e_{j_{1}},\ldots,e_{j_{\ell}}=e_{n}$,
$\ell\geq 1$, of distinct edges where the distance between two consecutive
edges in this sequence is $2$. Such a sequence is called a 2-step sequence of
length $\ell$.

Observe that there exists a partition of $E^{\prime}=E_{1}\cup\cdots\cup
E_{t}$, such that $E_{i}$, for every $i\in[t]$, consists of a maximal set of
edges such that between any two distinct edges $e_{j}$ and $e_{k}$ from
$E_{i}$ there exists a sequence
$e_{j}=e_{j_{0}},e_{j_{1}},\ldots,e_{j_{\ell}}=e_{k}$, $\ell\geq 1$, of
distinct edges such that the distance between two consecutive edges in this
sequence is $2$ (we call such sequence a 2-step sequence of length $\ell$).
Now, in $E_{i}$ fix an arbitrary edge $e$. For an arbitrary edge $f$ in
$E_{i}$ there exists a 2-step sequence between $e$ and $f$. Property $(iv)$
implies that the lengths of all different 2-step sequences between $e$ and $f$
are of the same parity. Thus, edges of $E_{i}$ can be partitioned into two
sets $E_{i}^{1}$ and $E_{i}^{2}$. The set $E_{i}^{1}$ consists of $e$ and all
edges $f$ for which the length of a 2-step sequence between $e$ and $f$ is
even, and $E_{i}^{2}=E_{i}-E_{i}^{1}$. For every $i\in[t]$ let $V_{i}^{1}$
denote the set of end-vertices of edges in $E_{i}^{1}$, and $V_{i}^{2}$ the
set of end-vertices of edges in $E_{i}^{2}$. Finally, let
$V_{1}=V_{1}^{1}\cup\cdots\cup V_{t}^{1}$ and $V_{2}=V_{1}^{2}\cup\cdots\cup
V_{t}^{2}$.

We will show that $\\{V_{0},V_{1},V_{2}\\}$ is a weak partition of $V(G)$
satisfying conditions (A), (B) and (C). Properties (B) and (C) clearly follow,
since $d_{G}(e_{i},e_{j})\geq 2$ for every pair $e_{i},e_{j}\in E^{\prime}$.
To prove (A) let $x\in V_{0}$. By $(iii)$ there exist exactly two different
edges $e_{p},e_{r}\in E^{\prime}$ such that $d_{G}(x,e_{p})=1=d_{G}(x,e_{r})$.
Note that $e_{p}$ and $e_{r}$ belong to the same $E_{i}$ in the partition of
$E^{\prime}$. Recall that we have fixed the edge $e\in E_{i}$. If a 2-step
sequence between $e$ and $e_{p}$ and a 2-step sequence between $e$ and $e_{r}$
have the same parity, then we obtain a contradiction with $(iv)$. Hence, end-
vertices of one edge, say $e_{p}$, belong to $V_{1}$, and end-vertices of
$e_{r}$ belong to $V_{2}$. Since, in addition, $N(u_{i})\cap
N(v_{i})=\emptyset$, by $(i)$ for every $i$ we have $|N(x)\cap
V_{1}|=1=|N(x)\cap V_{2}|$ and condition (A) holds.

######  Theorem 3.3.

Let $r$ be a positive integer such that $r>2$ and let $G$ be a graph. The
Cartesian product $G\,\Box\,K_{r}$ is an EOD-graph if and only if $G$ is a
$K_{r}$-amenable graph.

######  Proof 3.4.

Let $G$ be a $K_{r}$-amenable graph with corresponding weak partition
$\\{V_{0},\ldots,V_{r}\\}$ of $V(G)$. We define a subset $D$ of
$V(G\,\Box\,K_{r})$ by $D=\\{(g,i):i\in[r]\mbox{ and }g\in V_{i}\\}$. It
follows that $D$ contains at most one vertex from each $K_{r}$-layer. To prove
that $G\,\Box\,K_{r}$ is an EOD-graph we will show that every vertex of
$G\,\Box\,K_{r}$ is dominated by exactly one vertex of $D$. Let $i\in[r]$ and
let $g\in V(G)$. First, assume that $g\in V_{0}$. By (A), the vertex $g$ has a
unique neighbor $x_{i}$ in $V_{i}$. Consequently, $(g,i)$ is adjacent to
$(x_{i},i)$ and $(x_{i},i)\in D$. Moreover, by the uniqueness of $x_{i}$, no
other vertex of $D$ dominates $(g,i)$. Now assume that $g\in V_{i}$. Since
$\left\langle V_{i}\right\rangle$ is a perfect matching, $g$ has a unique
neighbor $g^{\prime}$ in $V_{i}$. It follows that $(g^{\prime},i)\in D$ and
that $(g^{\prime},i)$ is the only neighbor of $(g,i)$ in $D$. Finally, assume
that $g\in V_{j}$ for some $j\in[r]$ such that $j\neq i$. By the definition of
$D$ this implies that $\\{(g,j)\\}=D\cap\,^{g}K_{r}$. In addition, since (B)
and (C) hold, $(g,i)$ has no neighbor in $G^{i}\cap D$. The result is that
$(g,i)$ is dominated by exactly one vertex, namely $(g,j)$, of $D$.
Consequently, $D$ is an EOD-set of $G\,\Box\,K_{r}$ and $G\,\Box\,K_{r}$ is an
EOD-graph.

To prove the converse, suppose that $G\,\Box\,K_{r}$ is an EOD-graph with an
EOD-set $D$. For $i\in[r]$ let $V_{i}=\\{v\in V(G):(v,i)\in D\\}$, and let
$V_{0}=V(G)-(V_{1}\cup\cdots\cup V_{r})$. As we observed in Section 2, $D$ is
necessarily parallel with respect to $G$. This means that every ${}^{v}K_{r}$
contains at most one vertex of $D$, and we thus infer that
$\\{V_{0},V_{1},\ldots,V_{r}\\}$ is a weak partition of $V(G)$. We prove that
conditions (A), (B), and (C) of the definition of $K_{r}$-amenable hold. If
condition (A) is not satisfied, then there exist $x\in V_{0}$ and $i\in[r]$,
such that $|N(x)\cap V_{i}|=0$ or $|N(x)\cap V_{i}|>1$. In the first case
$(x,i)$ is not dominated by any vertex of $D$, and in the second case $(x,i)$
is dominated by more than one vertex of $D$. Both cases are in contradiction
with the assumption that $D$ is an EOD-set of $G\,\Box\,K_{r}$. Hence, the
weak partition $\\{V_{0},V_{1},\ldots,V_{r}\\}$ satisfies property (A). Let
$i\in[r]$ and let $g\in V_{i}$. Since $|D\cap\,^{g}K_{r}|\leq 1$ and $(g,i)$
has exactly one neighbor in $D$, it follows that
$|N(g)\cap(V_{1}\cup\cdots\cup V_{r})|=1=|N(g)\cap V_{i}|$. Hence, both (B)
and (C) hold. Therefore, $G$ is a $K_{r}$-amenable graph.

Let $r$ be an integer larger than 1. In the rest of this section we present a
recursive description of the family of all $K_{r}$-amenable trees. The
following construction generalizes the construction of zig-zag trees (that is,
$K_{2}$-amenable trees) from Kuziak et al. (2014b). We will denote by
$K_{1,r}^{+}$ the tree of order $2r+1$ obtained from the star $K_{1,r}$ by
subdividing each edge exactly once. It is clear that $K_{1,r}^{+}$ is a
$K_{r}$-amenable tree, and the corresponding partition of $V(K_{1,r}^{+})$ is
unique up to a permutation of $[r]$. We now define an infinite family
$\mathcal{T}_{r}$ of trees. Each member of $\mathcal{T}_{r}$ will have a weak
partition $\\{V_{0},V_{1},\ldots,V_{r}\\}$ of its vertex set associated with
it.

Suppose that $T^{\prime}$ is a tree of order $n$ such that
$\\{V^{\prime}_{0},V^{\prime}_{1},\ldots,V^{\prime}_{r}\\}$ is a weak
partition of $V(T^{\prime})$ and that $T^{\prime\prime}$ is a tree of order
$m$ such that
$\\{V^{\prime\prime}_{0},V^{\prime\prime}_{1},\ldots,V^{\prime\prime}_{r}\\}$
is a weak partition of $V(T^{\prime\prime})$.

We say that a tree $T$ of order $n+m-2$ is obtained from $T^{\prime}$ and
$T^{\prime\prime}$ by a Type-a construction if $T$ is isomorphic to the tree
formed by choosing any $i\in[r]$, any edge $u^{\prime}_{i}v^{\prime}_{i}$ in
$\left\langle V^{\prime}_{i}\right\rangle$, any edge
$u^{\prime\prime}_{i}v^{\prime\prime}_{i}$ in $\left\langle
V^{\prime\prime}_{i}\right\rangle$ and then identifying the vertices
$u^{\prime}_{i}$ with $u^{\prime\prime}_{i}$ (now called $u_{i}$) and
$v^{\prime}_{i}$ with $v^{\prime\prime}_{i}$ (now called $v_{i}$) to obtain
the edge $u_{i}v_{i}$ in $T$. The associated weak partition
$\\{V_{0},V_{1},\ldots,V_{r}\\}$ of $V(T)$ is defined by
$V_{j}=V^{\prime}_{j}\cup V^{\prime\prime}_{j}$ if $j\neq i$, and
$V_{i}=(V^{\prime}_{i}\cup
V^{\prime\prime}_{i}\cup\\{u_{i},v_{i}\\})-\\{u^{\prime}_{i},v^{\prime}_{i},u^{\prime\prime}_{i},v^{\prime\prime}_{i}\\}$.

A tree $S$ of order $n+m$ is obtained from $T^{\prime}$ and $T^{\prime\prime}$
by a Type-b construction if $S$ is isomorphic to the tree formed from the
union of $T^{\prime}$ and $T^{\prime\prime}$ by adding an edge $xy$ for some
$x\in V^{\prime}_{0}$ and some $y\in V^{\prime\prime}_{0}$. The associated
weak partition $\\{V_{0},V_{1},\ldots,V_{r}\\}$ of $V(S)$ is given by
$V_{i}=V^{\prime}_{i}\cup V^{\prime\prime}_{i}$ for $0\leq i\leq r$.

The family $\mathcal{T}_{r}$ is defined recursively as follows. A tree $T$
belongs to $\mathcal{T}_{r}$ if and only if $T=K_{1,r}^{+}$ with its partition
as indicated above or $T$ can be obtained from smaller trees in
$\mathcal{T}_{r}$ by a finite sequence of Type-a or Type-b constructions.

######  Theorem 3.5.

Let $r$ be an integer such that $r\geq 2$. The path of order 2 is
$K_{r}$-amenable. If $T$ is a tree of order more than 2, then $T$ is a
$K_{r}$-amenable graph if and only if $T\in\mathcal{T}_{r}$.

######  Proof 3.6.

Let $r$ be an integer such that $r\geq 2$. For the path of order 2, let
$V_{1}=V(P_{2})$, $V_{0}=\emptyset=V_{i}$ for $2\leq i\leq r$. This weak
partition $\\{V_{0},V_{1},\ldots,V_{r}\\}$ satisfies the definition showing
that $P_{2}$ is a $K_{r}$-amenable graph. For the remainder of this proof we
assume that all trees under consideration have order at least 3. As noted
above, the tree $K_{1,r}^{+}$ is a $K_{r}$-amenable tree. One can conclude
directly from the definitions that if $T^{\prime}$ and $T^{\prime\prime}$ are
both $K_{r}$-amenable trees, then a tree obtained from $T^{\prime}$ and
$T^{\prime\prime}$ by a Type-a or a Type-b construction is also a
$K_{r}$-amenable graph. Thus, it follows by induction (on the number of Type-a
and Type-b constructions) that every member of $\mathcal{T}_{r}$ is a
$K_{r}$-amenable graph.

Conversely, let $T$ be a $K_{r}$-amenable tree of order at least 3 with a
corresponding weak partition $\\{V_{0},V_{1},\ldots,V_{r}\\}$ and let
$k=|V_{0}|$. Since $T$ has order at least 3, it follows from the definition
that $k\geq 1$. We use induction on $k$ to show that $T\in\mathcal{T}_{r}$.
Let $k=1$ and $V_{0}=\\{v\\}$. By property (A) $\deg(v)=r$; let
$N(v)=\\{u_{1},\ldots,u_{r}\\}$ where $u_{i}\in V_{i}$. By (B) every $u_{i}$
has a unique neighbor $w_{i}$ in $V_{i}$ and by (C) $u_{i}$ and $w_{i}$ have
no neighbors in $V_{j}$ for $j\neq i$. Moreover, $u_{i}$ and $w_{i}$ have no
additional neighbors in $V_{0}$ since $k=1$. Thus, $T$ is isomorphic to
$K_{1,r}^{+}$ and hence $T\in\mathcal{T}_{r}$.

Now suppose that $k>1$. Note that every vertex in $V_{0}$ has degree at least
$r$. If there exists $v\in V_{0}$ with $\deg(v)>r$, then there exists $w\in
V_{0}\cap N(v)$. Let $T^{\prime}$ be the component of $T-vw$ that contains $v$
and let $T^{\prime\prime}$ be the component that contains $w$. For $0\leq
i\leq r$, let $V_{i}^{\prime}=V_{i}\cap V(T^{\prime})$ and let
$V_{i}^{\prime\prime}=V_{i}\cap V(T^{\prime\prime})$. The resulting weak
partitions of $V(T^{\prime})$ and $V(T^{\prime\prime})$ clearly satisfy
properties (A), (B) and (C), and furthermore $|V_{0}^{\prime}|<k$ and
$|V_{0}^{\prime\prime}|<k$. By the induction hypothesis both $T^{\prime}$ and
$T^{\prime\prime}$ belong to $\mathcal{T}_{r}$. Since $T$ is obtained from
$T^{\prime}$ and $T^{\prime\prime}$ by a Type-b construction, it follows that
$T\in\mathcal{T}_{r}$.

Now, suppose that all vertices of $V_{0}$ are of degree $r$ (and hence
$\left\langle V_{0}\right\rangle$ contains no edges). Choose $u$ and $v$ from
$V_{0}$ with the property that $d_{T}(u,v)$ is minimum among all different
pairs of vertices from $V_{0}$. Clearly, $2\leq d_{T}(u,v)\leq 3$. Let $w$ be
the neighbor of $u$ on the shortest $u,v$-path in $T$. Without loss of
generality we may assume that $w\in V_{1}$. By (B), $w$ has a unique neighbor,
say $w^{\prime}$, in $V_{1}$. The forest $T-uw$ has two connected components.
The component that contains $u$ is denoted by $T_{u}$ and the one that
contains $v$ is denoted by $T^{\prime\prime}$. Let $T^{\prime}$ be the tree
obtained from $T_{u}$ by adding vertices $t$ and $t^{\prime}$ and adding edges
$ut$ and $tt^{\prime}$. Let $V_{i}^{\prime\prime}=V_{i}\cap
V(T^{\prime\prime})$ for $0\leq i\leq r$, let $V_{1}^{\prime}=(V_{1}\cap
V(T_{u}))\cup\\{t,t^{\prime}\\}$, and let $V_{i}^{\prime}=V_{i}\cap V(T_{u})$
for $i=0$ and $2\leq i\leq r$. Properties (A), (B) and (C) clearly hold for
the above defined weak partitions of $V(T^{\prime})$ and
$V(T^{\prime\prime})$. Thus, $T^{\prime}$ and $T^{\prime\prime}$ are
$K_{r}$-amenable trees. By the induction hypothesis, they are also in
$\mathcal{T}_{r}$. Note that $T$ is isomorphic to the tree obtained from
$T^{\prime}$ and $T^{\prime\prime}$ by a Type-a construction that identifies
$t$ with $w$, and $t^{\prime}$ with $w^{\prime}$. Consequently,
$T\in\mathcal{T}_{r}$.

This theorem together with Theorem 3.3 combine to give us the following
characterization of those trees $T$ such that $T\,\Box\,K_{r}$ is an EOD-graph
for $r\geq 3$.

######  Corollary 3.7.

Let $r$ be a positive integer larger than 2 and let $T$ be a tree. The
Cartesian product $T\,\Box\,K_{r}$ is an EOD-graph if and only if $T=P_{2}$ or
$T\in\mathcal{T}_{r}$.

##  4 $G\,\Box\,H$ with diam$(H)=2$

In this section we consider Cartesian products of graphs where (at least) one
factor has diameter $2$. Motivation for the study of such graphs arises from
the previous section. An EOD-set of $G\,\Box\,H$ that is parallel with respect
to $G$ when $\mathrm{diam}(H)=2$ shares an important property with such a set
in $G\,\Box\,K_{r}$ for $r\geq 3$. This is given in the following lemma.

######  Lemma 4.1.

Let $H$ be a graph of diameter 2 and let $G$ be a graph such that $G\,\Box\,H$
has an EOD-set $D$. For every vertex $g$ in $G$, $|D\cap\,^{g}H|\leq 2$. If in
addition $D$ is parallel with respect to $G$, then $|D\cap\,^{g}H|\leq 1$ for
every $g\in V(G)$. If $|D\cap\,^{g}H|=2$, then the two distinct vertices in
$D\cap\,^{g}H$ are adjacent.

######  Proof 4.2.

Assume that $D$ is an EOD-set of $G\,\Box\,H$ and suppose that $(g,u)$ and
$(g,v)$ are distinct vertices in $D$. The graph $H$ has diameter 2, and this
implies that $uv\in E(H)$ or $u$ and $v$ have a common neighbor $w$ in $H$.
Since every vertex in ${}^{g}H$ is dominated exactly once by $D$, we infer
that $(g,u)$ and $(g,v)$ are adjacent, and $|D\cap\,^{g}H|\leq 2$. It follows
immediately that if $D$ is parallel with respect to $G$, then no $H$-layer can
contain two members of $D$. $\,\Box\,$

As we will see, finding an appropriate weak partition of vertices in $G$ will
be useful in the characterization of (parallel) EOD-graphs among Cartesian
products $G\,\Box\,H$ where $\mathrm{diam}(H)=2$. First we show that the
Cartesian product of a graph of diameter $2$ and a tree on at least three
vertices does not admit a parallel EOD-set with respect to the tree.

######  Theorem 4.3.

Let $H$ be a graph with $\mathrm{diam}(H)=2$ and let $T$ be a tree. If $T$ is
different than $K_{2}$, then $T\,\Box\,H$ does not contain a parallel EOD-set
with respect to $T$.

######  Proof 4.4.

Let $H$ be a graph with $\mathrm{diam}(H)=2$. Suppose, in order to obtain a
contradiction, that there exists a tree $T$ different than $K_{2}$, such that
$T\,\Box\,H$ admits a parallel EOD-set $D$ with respect to $T$.

First, we claim that $T^{h}\cap D=\emptyset$ for every non-universal vertex
$h$ in $H$. If this does not hold, then there exist vertices
$(u_{0},h),(v_{0},h)\in D$ which are adjacent in $T\,\Box\,H$. Since $h$ is
not universal in $H$, there is $h^{\prime}\in V(H)$ such that
$d_{H}(h,h^{\prime})=2$. Observe that $(u_{0},h^{\prime})$ and
$(v_{0},h^{\prime})$ are not dominated by $(u_{0},h)$ and $(v_{0},h)$.
Moreover, they are not dominated by any vertex in ${}^{u_{0}}\\!H$ and
${}^{v_{0}}\\!H$ (since $\mathrm{diam}(H)=2$ we have that $|^{x}H\cap D|\leq
1$ for every $x\in V(T)$ by Lemma 4.1). Therefore, there exists a neighbor
$u_{1}$ of $u_{0}$ and a neighbor $v_{1}$ of $v_{0}$, such that
$(u_{0},h^{\prime})$ is dominated by $(u_{1},h^{\prime})\in D$ and
$(v_{0},h^{\prime})$ is dominated by $(v_{1},h^{\prime})\in D$. Moreover,
since $(u_{1},h^{\prime}),(v_{1},h^{\prime})\in D$, there exist
$(u_{2},h^{\prime}),(v_{2},h^{\prime})\in D$, where $u_{2}u_{1},v_{2}v_{1}\in
E(T)$. To dominate vertices $(u_{2},h)$ and $(v_{2},h)$, there must exist
$(u_{3},h),(v_{3},h)\in D$ where $u_{3}u_{2},v_{3}v_{2}\in E(T)$. Continuing
in this way we obtain a two-way infinite walk $\ldots
u_{2}u_{1}u_{0}v_{0}v_{1}v_{2}\ldots$ in $T$. Since $T$ is a tree, all
vertices of this walk are pairwise different. But this is in contradiction
with $T$ being finite, and the claim is proved.

We infer that $H$ has to contain universal vertices and that the projection of
every edge in $\left\langle D\right\rangle$ onto $H$ is a universal vertex.
Now, let $h$ be a universal vertex of $H$, such that $T^{h}\cap
D\neq\emptyset$ and let $(u,h),(v,h)\in D$ be adjacent vertices. Together they
dominate all vertices of ${}^{u}H$ and ${}^{v}H$. There also exists a non-
universal vertex $h^{\prime}$ in $H$ because $\mathrm{diam}(H)=2$. Since $T$
is different than $K_{2}$, at least one of $u$ and $v$, say $u$, has a
neighbor $w$ in $T$. Note that $(w,h)$ is dominated by $(u,h)$, and
$(w,h^{\prime})$ is not dominated by $(u,h)$ nor $(v,h)$. Since
$T^{h^{\prime}}\cap D=\emptyset$, there exists another universal vertex
$h_{1}\in V(H)$, such that $(w,h^{\prime})$ is dominated by $(w,h_{1})\in D$.
This yields a final contradiction, since $(w,h)$ is dominated by both $(u,h)$
and $(w,h_{1})$ from $D$, which is not possible in an EOD-set $D$.

###  4.1 $G\,\Box\,K_{m,n}$

In this subsection we give a necessary and sufficient condition on a graph $G$
such that $G\,\Box\,K_{m,n}$ is an EOD-graph for $1\leq m\leq n$. The
condition will be the existence of a weak partition of $V(G)$ that satisfies
very specific requirements. While it may not be easy to determine whether a
given graph $G$ has such a weak partition, the requirements of the weak
partition will make it straightforward to construct graphs $G$ such that
$G\,\Box\,K_{m,n}$ is an EOD-graph.

Since $K_{m,n}$ has diameter 2 and we are not requiring the EOD-set of
$G\,\Box\,K_{m,n}$ to be parallel with respect to $G$, we will refer often to
Lemma 4.1. For ease of explanation we assume throughout this subsection that
$1\leq m\leq n$ and that $K_{m,n}$ has partite sets $A$ and $B$ given by
$A=\\{1,\ldots,m\\}$ and $B=\\{m+1,\ldots,m+n\\}$. With this notation we let
$\mathcal{C}_{m,n}$ be a weak partition of $V(G)$ containing $mn+m+n+1$ parts
indexed as follows:

  * •

$V_{0},V_{1},\ldots,V_{m},V_{m+1},\ldots,V_{m+n}$; and

  * •

$V_{[i,m+j]}$ for $1\leq i\leq m$ and $1\leq j\leq n$.

We will say that $\mathcal{C}_{m,n}$ is _$K_{m,n}$ -amenable_ if it is a weak
partition satisfying the following conditions.

  * (I)

For $1\leq i\leq m+n$, the induced subgraph $\left\langle V_{i}\right\rangle$
is a matching.

  * (II)

For $1\leq i\leq m$ and $m+1\leq j\leq m+n$, $\left\langle V_{i}\cup
V_{j}\right\rangle$ is a matching.

  * (III)

For $1\leq i<j\leq m$ or $m+1\leq i<j\leq m+n$, each $x$ in $V_{i}$ has
exactly one neighbor in $V_{j}$ and each $y$ in $V_{j}$ has exactly one
neighbor in $V_{i}$.

  * (IV)

If $x\in V_{[i,m+j]}$ for some $1\leq i\leq m$ and some $1\leq j\leq n$, then
$N(x)\subseteq V_{0}$.

  * (V)

If $x\in V_{0}$, then $|N(x)\cap\left(\cup_{1\leq j\leq n}V_{[i,m+j]}\cup
V_{i}\right)|=1$ for $1\leq i\leq m$, and
$|N(x)\cap\left(\cup_{1\leq i\leq m}V_{[i,m+j]}\cup V_{m+j}\right)|=1$ for
$1\leq j\leq n$.

A graph $G$ will be called _$K_{m,n}$ -amenable_ if $V(G)$ has a weak
partition that is $K_{m,n}$-amenable. With this definition we are now able to
give a constructive characterization of those graphs $G$ such that
$G\,\Box\,K_{m,n}$ is an EOD-graph.

######  Theorem 4.5.

Let $m$ and $n$ be positive integers such that $m\leq n$ and let $G$ be a
graph. The Cartesian product $G\,\Box\,K_{m,n}$ is an EOD-graph if and only if
$G$ is $K_{m,n}$-amenable.

######  Proof 4.6.

Assume that $G$ is $K_{m,n}$-amenable and that $\mathcal{C}_{m,n}$ is a weak
partition of $V(G)$ indexed as above and satisfying the conditions (I)-(V) in
the definition above. We define a subset $D$ of $V(G\,\Box\,K_{m,n})$ by
specifying its intersection with each $K_{m,n}$-layer. If $r$ is an integer
such that $1\leq r\leq m+n$ and $g\in V_{r}$, then
$D\cap\,^{g}K_{m,n}=\\{(g,r)\\}$. If $r$ and $s$ are integers with $1\leq
r\leq m$ and $1\leq s\leq n$ such that $g\in V_{[r,m+s]}$, then
$D\cap\,^{g}K_{m,n}=\\{(g,r),(g,m+s)\\}$. Finally, if $g\in V_{0}$, then
$D\cap\,^{g}K_{m,n}=\emptyset$. Since $\mathcal{C}_{m,n}$ is a weak partition,
the set $D$ is well-defined. We now show that $D$ is an EOD-set of
$G\,\Box\,K_{m,n}$ by showing that each vertex of $G\,\Box\,K_{m,n}$ has
exactly one neighbor in $D$.

Let $(x,t)$ be an arbitrary vertex in $G\,\Box\,K_{m,n}$. Assume $x\in V_{0}$.
Suppose first that $1\leq t\leq m$. By (V) there exists $y\in V(G)$ such that
$\\{y\\}=N(x)\cap\left(\cup_{1\leq j\leq n}V_{[t,m+j]}\cup V_{t}\right)$. This
implies that $(y,t)\in D$ and that $(y,t)$ dominates $(x,t)$. Furthermore, it
follows from (V) and $D\cap\,^{x}K_{m,n}=\emptyset$ that $(y,t)$ is the only
neighbor of $(x,t)$ that belongs to $D$. The case $m+1\leq t\leq m+n$ is
similar. Assume next that $x\in V_{[r,m+s]}$ for some $r$ and $s$ such that
$1\leq r\leq m$ and $1\leq s\leq n$. By the definition of $D$ we get that both
$(x,r)$ and $(x,m+s)$ belong to $D$. Exactly one of these is adjacent to
$(x,t)$. Combining this with property (IV) it follows that $(x,t)$ has exactly
one neighbor in $D$. Finally, assume that $x\in V_{r}$ for some $r$ with
$1\leq r\leq m$. (The case $m+1\leq r\leq m+n$ is similar.) This means that
$(x,r)\in D$ and $|D\cap\,^{x}K_{m,n}|=1$. There are three subcases to
consider, namely (i) $m+1\leq t\leq m+n$, (ii) $t=r$, and (iii) $t\neq r$ but
$1\leq t\leq m$. If $m+1\leq t\leq m+n$, then $(x,r)$ dominates $(x,t)$ (from
within the layer ${}^{x}K_{m,n}$). From (I), (II) and (IV) we see that $(x,t)$
is not adjacent to any vertex in $D\cap G^{t}$. Thus, in subcase (i) $(x,t)$
has a unique neighbor in $D$. Assume that $t=r$. By (I) there is a unique
$y\in V_{r}\cap N(x)$. By definition $(y,r)\in D$ and thus $(x,r)$ is
dominated by $D$. Properties (I) and (IV) together imply that $(x,t)$ has no
other neighbor in $D$. Finally, assume subcase (iii) holds. By (III) there
exists a unique $z\in V_{t}\cap N(x)$. Now $(z,t)\in D$ and $(x,t)$ is
dominated by $(z,t)$. Consequently, by (IV) it follows that $(z,t)$ is the
only vertex in $D$ that dominates $(x,t)$. We have shown that $D$ is an EOD-
set of $G\,\Box\,K_{m,n}$.

Conversely, suppose that $S$ is an EOD-set of $G\,\Box\,K_{m,n}$. Since
$K_{m,n}$ has diameter 2, we apply Lemma 4.1 and conclude that
$|S\cap\,^{g}K_{m,n}|\leq 2$ for every vertex $g$ in $G$. We produce a weak
partition $\mathcal{C}$ of $V(G)$ as follows. The sets in $\mathcal{C}$ are
those in the following specifications. Note that some of these subsets might
be empty.

  * •

$V_{0}=\\{x\in V(G):S\cap\,^{x}K_{m,n}=\emptyset\\}$,

  * •

$V_{i}=\\{x\in V(G):S\cap\,^{x}K_{m,n}=\\{(x,i)\\}\\}$ for $1\leq i\leq m+n$,

  * •

$V_{[i,m+j]}=\\{x\in V(G):S\cap\,^{x}K_{m,n}=\\{(x,i),(x,m+j)\\}\\}$ for
$1\leq i\leq m$ and $1\leq j\leq n$.

The verification that $\mathcal{C}$ is $K_{m,n}$-amenable (that is, it
satisfies properties (I)-(V)) follows directly from the assumption that $S$ is
an EOD-set of $G\,\Box\,K_{m,n}$ and is left to the reader.

$0$$[2,5]$$5$$5$$3$$3$$4$$4$$1$$1$$2$$2$ Figure 1: A $K_{2,3}$-amenable graph
$G$

The graph $G$ in Figure 1 was constructed to have a weak partition that is
$K_{2,3}$-amenable. The partite sets of $K_{2,3}$ are as in the development
above, $A=\\{1,2\\}$ and $B=\\{3,4,5\\}$. For simplicity the vertices of $G$
are labeled to indicate the subset of the weak partition that contains them.
For example, the vertices labeled $1$ are in $V_{1}$ while the vertex labeled
$[2,5]$ is the only member of $V_{[2,5]}$. By Theorem 4.5 the Cartesian
product $G\,\Box\,K_{2,3}$ is an EOD-graph.

###  4.2 $G\,\Box\,C_{r},r\in\\{4,5\\}$

In this subsection we first define a type of weak partition of $V(G)$ that
will enable us to characterize those Cartesian products $G\,\Box\,C_{5}$ that
are parallel EOD-graphs with respect to $G$. To describe these weak partitions
we need to modify Condition (C) as it was stated in Section 3 and add an
additional condition. The operations on the subscripts in these new conditions
are made modulo $5$.

  * (C′)

$\left\langle V_{i}\cup V_{i+1}\right\rangle$ is a matching in $G$ for every
$i\in[5]$,

  * (D)

if $x\in V_{i}$, then $|N(x)\cap V_{i+2}|=1$ and $|N(x)\cap V_{i-2}|=1$ for
every $i\in[5]$.

Notice that the condition (C′) is weaker than (C). We say that $G$ is _$C_{5}$
-parallel amenable_ if there exists a weak partition
$\\{V_{0},V_{1},V_{2},V_{3},V_{4},V_{5}\\}$ of $V(G)$ that satisfies
conditions (A), (B), (C′) and (D).

######  Theorem 4.7.

For any graph $G$, the Cartesian product $G\,\Box\,C_{5}$ is a parallel EOD-
graph with respect to $G$ if and only if $G$ is a $C_{5}$-parallel amenable
graph.

######  Proof 4.8.

Assume first that $G$ is a $C_{5}$-parallel amenable graph and let
$\\{V_{0},V_{1},V_{2},V_{3},V_{4},V_{5}\\}$ be a weak partition of $V(G)$ that
satisfies conditions (A), (B), (C′) and (D). We define a subset $D$ of
$V(G\,\Box\,C_{5})$ by $D=\\{(g,i):g\in V_{i}\,\,\mbox{for}\,\,i\in[5]\\}$.
Notice that $|D\cap\,^{g}C_{5}|=1$ for every $g\in V(G)-V_{0}$. We will show
that every vertex of $G\,\Box\,C_{5}$ is dominated by exactly one vertex of
$D$. Let $(g,j)$ be an arbitrary vertex of $G\,\Box\,C_{5}$.

Assume first that $g\in V_{i}$ for some $i\in[5]$. If $j\in\\{i-1,i+1\\}$,
then $(g,j)$ is dominated by $(g,i)$. Moreover, $(g,j)$ is dominated only by
$(g,i)$ in $D$, since $(g,i)$ is the only vertex in $D\cap\,^{g}C_{5}$ and (B)
and (C′) hold. If $j=i$, then $(g,j)$ is dominated by $(g^{\prime},i)$, where
$gg^{\prime}$ is an edge in $\left\langle V_{i}\right\rangle$ (notice that
$g^{\prime}$ exists by (B)). Note that $(g,j)$ is dominated only by
$(g^{\prime},i)$ from $D$ by (B) and the fact that $|D\cap\,^{g}C_{5}|=1$. It
remains to consider $j=i+2$ and $j=i-2$. Assume $j=i+2$; the case $j=i-2$ is
similar. By condition (D), $g$ has a unique neighbor $x_{i+2}\in V_{i+2}$. By
definition $(x_{i+2},i+2)\in D$, and thus $(x_{i+2},i+2)$ dominates $(g,j)$.
As before, since $|D\cap\,^{g}C_{5}|=1$ and since condition (D) holds, it
follows that $(x_{i+2},i+2)$ is the only vertex of $D$ that dominates $(g,j)$.
Hence, if $g\in V_{i}$ for some $i\in[5]$, then $(g,j)$ is dominated exactly
once by $D$. Finally, assume that $g\in V_{0}$. By condition (A), $g$ has a
unique neighbor $x_{j}\in V_{j}$. This implies that $(x_{j},j)\in D$ and that
$(x_{j},j)$ is the only vertex in $D$ that dominates $(g,j)$. Consequently,
$D$ is a parallel EOD-set of $G\,\Box\,C_{5}$.

Conversely, let $G\,\Box\,C_{5}$ be a parallel EOD-graph and let $D$ be a
parallel EOD-set with respect to $G$. Let
$V_{0},V_{1},V_{2},V_{3},V_{4},V_{5}$ be subsets of $V(G)$ defined as follows.
If $|D\cap\,^{g}C_{5}|=0$, then $g\in V_{0}$. For $i\in[5]$, $g\in\,V_{i}$ if
and only if $\\{(g,i)\\}=D\cap\,^{g}C_{5}$. By Lemma 4.1,
$|D\cap\,^{g}C_{5}|\leq 1$ for every $g\in V(G)$, and thus
$\\{V_{0},V_{1},V_{2},V_{3},V_{4},V_{5}\\}$ is a weak partition of $V(G)$.
Note that only $V_{0}$ can be empty.

We will show that this weak partition satisfies conditions (A), (B), (C′) and
(D). If (A) does not hold, then there exists a vertex $(g,i)$ where
$|D\cap\,^{g}C_{5}|=0$ and either $|N(g)\cap V_{i}|=0$ or $|N(g)\cap V_{i}|>1$
for some $i\in[5]$. In the first case $(g,i)$ is not dominated by $D$ and in
the second case $(g,i)$ is dominated by at least two vertices, both
contradicting the fact that $D$ is a parallel EOD-set. Thus, (A) holds. If (B)
is not satisfied, then there exists $g\in V_{i}$, for some $i\in[5]$, such
that either $\deg_{\left\langle V_{i}\right\rangle}(g)=0$ or
$\deg_{\left\langle V_{i}\right\rangle}(g)>1$, which yields exactly the same
contradiction as for (A). Hence, (B) is true as well. If (C′) does not hold,
then there exist $g\in V_{i}$ and $g^{\prime}\in V_{i+1}$ for some $i\in[5]$,
such that $gg^{\prime}\in E(G)$. We infer that $(g,i+1)$ is dominated twice,
that is by $(g,i)$ and by $(g^{\prime},i+1)$, which is not possible. Finally,
if (D) does not hold, then for some $i\in[5]$, there exists $x\in V_{i}$ such
that $|N(x)\cap V_{i+2}|\neq 1$ or $|N(x)\cap V_{i-2}|\neq 1$. Again we get
that some vertex is not dominated by $D$ (if $|N(x)\cap V_{i+2}|=0=|N(x)\cap
V_{i-2}|$) or that some vertex is dominated more than once by $D$ (if
$|N(x)\cap V_{i+2}|>1$ or $|N(x)\cap V_{i-2}|>1$), which is not possible. This
shows that (D) is also true, which completes the proof.

While the complete characterization of EOD Cartesian products where one factor
is $C_{4}\cong K_{2,2}$ was given in Subsection 4.1, here we describe all $G$
such that $G\,\Box\,C_{4}$ is a parallel EOD-graph with respect to $G$. For
$C_{4}$ notice that computations on the subscripts are done modulo $4$ in the
set $[4]$, and in this case $i+2=i-2$. Thus, we can restate condition (D) as

  * (D′)

if $x\in V_{i}$, then $|N(x)\cap V_{i+2}|=1$ for every $i\in[4]$.

We say that $G$ is $C_{4}$-parallel amenable if there exists a weak partition
$\\{V_{0},V_{1},V_{2},V_{3},V_{4}\\}$ of $V(G)$ that fulfills conditions (A),
(B), (C′) and (D′). The proof of the following theorem follows the same lines
as the proof of Theorem 4.7 if we take into consideration computation modulo
$4$ instead of modulo $5$.

######  Theorem 4.9.

For any graph $G$, the Cartesian product $G\,\Box\,C_{4}$ is a parallel EOD-
graph with respect to $G$ if and only if $G$ is a $C_{4}$-parallel amenable
graph.

For $r\in\\{4,5\\}$ there exist many graphs $G$ which are not $C_{r}$-parallel
amenable, but for which $G\,\Box\,C_{4}$ is an EOD-graph (clearly
$G\,\Box\,C_{4}$ is not a parallel EOD-graph with respect to $G$ in this
case). One of the smallest examples is $P_{3}$, which is not $C_{4}$-parallel
amenable, but $P_{3}\,\Box\,C_{4}$ is an EOD-graph, even a parallel EOD-graph
with respect to $C_{4}$.

##  5 Conclusion

As already mentioned, this method of defining weak partitions is most easily
implemented when one of the graphs has small diameter. Despite this fact,
there is no reason why one should not use it on graphs with larger diameter.
We illustrate this idea on a special case from the class of cycles.

Our goal is to define a weak partition of a graph $G$ that consists of $V_{0}$
and a family of sets $V_{A}$ where $A$ is a subset of $[k]$ with certain
properties. We derive these properties from the second graph in the product,
which is $C_{k}$ now. Again we have two possibilities for an edge from
$\left\langle D\right\rangle$, where $D$ is an EOD-set of $G\,\Box\,C_{k}$:
either it projects to $C_{k}$ as an edge or as a vertex. If it projects to an
edge in $C_{k}$, then $A$ must contain two consecutive elements $i$ and $i+1$.
If an edge projects to a single vertex $j\in V(C_{k})$, then $j\in A$ but
neither $j+1$ nor $j-1$ is in $A$. Moreover, two non-consecutive elements of
$A$ must differ by at least 3 modulo $k$, so that no vertex in the product is
dominated more than once.

$[1,2]$$[1,2]$$[4,5]$$0$$[4,5]$$0$$[3,6]$$[3,6]$ Figure 2: A
“$C_{6}$-amenable” graph $G$

In particular, for $C_{6}$ we obtain the following weak partition:

$V_{0},V_{1},V_{2},V_{3},V_{4},V_{5},V_{6},V_{[1,2]},V_{[2,3]},V_{[3,4]},V_{[4,5]},V_{[5,6]},V_{[6,1]},V_{[1,4]},V_{[2,5]},V_{[3,6]}\,.$

Clearly the size of the weak partition increases with $k$. Together with this
weak partition, several conditions are needed as well. For instance we need a
condition similar to (A) and (V) to care about all vertices from $V_{0}$. As
in the case of $K_{2,3}$-amenable graphs, it seems to be hard to decide
whether a graph $G$ is a “$C_{k}$-amenable” graph. However, it is not
difficult to construct (small) examples of such graphs. An example of a
“$C_{6}$-amenable” graph is given in Figure 2. The labeling follows the
prescription given for Figure 1.

## References

  * Abay-Asmerom et al. (2008) G. Abay-Asmerom, R. H. Hammack, and D. T. Taylor.  Total perfect codes in tensor products of graphs.  _Ars Combinatoria_ , 88:129–134, 2008.  URL https://www.scopus.com/inward/record.uri?eid=2-s2.0-47949133881&partnerID=40&md5=82cb6dcced332d41ac19d49db5afcd5f.  cited By 4.
  * Biggs (1973) N. Biggs.  Perfect codes in graphs.  _Journal of Combinatorial Theory, Series B_ , 15(3):289–296, 1973.  10.1016/0095-8956(73)90042-7.  URL https://www.scopus.com/inward/record.uri?eid=2-s2.0-0001058806&partnerID=40&md5=8578eda2f5f5ed2464c88eac313b1b54.  cited By 84.
  * Brešar et al. (2012) B. Brešar, P. Dorbec, W. Goddard, B. L. Hartnell, M. A. Henning, S. Klavžar, and A. D. F. Rall.  Vizing’s conjecture: A survey and recent results.  _Journal of Graph Theory_ , 69(1):46–76, 2012\.  10.1002/jgt.20565.  URL https://www.scopus.com/inward/record.uri?eid=2-s2.0-81955168121&partnerID=40&md5=714c9283eb2c834b7444bff2f12fafd9.  cited By 19.
  * Cockayne et al. (1993) E. J. Cockayne, B. L. Hartnell, S. T. Hedetniemi, and R. Laskar.  Perfect domination in graphs.  _Journal of Combinatorics, Information and System Sciences_ , 18:136–148, 1993.
  * Cowen et al. (2007) R. Cowen, S. H. Hechler, J. W. Kennedy, and A. Steinberg.  Odd neighborhood transversals on grid graphs.  _Discrete Mathematics_ , 307(17-18):2200–2208, 2007.  10.1016/j.disc.2006.11.006.  URL https://www.scopus.com/inward/record.uri?eid=2-s2.0-34447096089&partnerID=40&md5=4ef158d7008e574c74c14480be62a3e4.  cited By 1.
  * Dejter (2008) I. J. Dejter.  Perfect domination in regular grid graphs.  _Australasian Journal of Combinatorics_ , 42:99–114, 2008\.  URL https://www.scopus.com/inward/record.uri?eid=2-s2.0-77956497962&partnerID=40&md5=5ee0089c7962e1b1c450d7cc2c7273fb.  cited By 7.
  * Dorbec et al. (2006) P. Dorbec, S. Gravier, S. Klavžar, and S. Špacapan.  Some results on total domination in direct products of graphs.  _Discussiones Mathematicae Graph Theory_ , 26:103–112, 2006\.
  * Gavlas and Schultz (2002) H. Gavlas and K. Schultz.  Efficient open domination.  _Electronic Notes in Discrete Mathematics_ , 11:681–691, 2002.  10.1016/S1571-0653(04)00113-1.  URL https://www.scopus.com/inward/record.uri?eid=2-s2.0-34247126166&partnerID=40&md5=d7e81725fdb979fd7b8b1f6db56bff30.  cited By 5.
  * Gavlas et al. (2003) H. Gavlas, K. Schultz, and P. Slater.  Efficient open domination in graphs.  _Scientia. Series A. Mathematical Sciences. New Series_ , 6:77–84, 2003.
  * Gravier (2002) S. Gravier.  Total domination number of grid graphs.  _Discrete Applied Mathematics_ , 121(1-3):119–128, 2002.  10.1016/S0166-218X(01)00297-9.  URL https://www.scopus.com/inward/record.uri?eid=2-s2.0-84867954416&partnerID=40&md5=352b54fa6d26558f57889941928b0f01.  cited By 21.
  * Hammack et al. (2012) R. Hammack, W. Imrich, and S. Klavžar.  _Handbook of Product Graphs_.  CRC Press, Boca Raton, 2012.
  * Henning and Rall (2005) M. A. Henning and D. F. Rall.  On the total domination number of cartesian products of graphs.  _Graphs and Combinatorics_ , 21(1):63–69, 2005\.  10.1007/s00373-004-0586-8.  URL https://www.scopus.com/inward/record.uri?eid=2-s2.0-17144421208&partnerID=40&md5=e3cf8a8fce6eb1f1e949164a1db085d4.  cited By 13.
  * Ho (2008) P. T. Ho.  A note on the total domination number.  _Utilitas Mathematica_ , 77:97–100, 2008.  URL https://www.scopus.com/inward/record.uri?eid=2-s2.0-57049085820&partnerID=40&md5=070fdc1064b24b409f25d4185e902dc4.  cited By 6.
  * Jerebic et al. (2005) J. Jerebic, S. Klavžar, and S. Špacapan.  Characterizing r-perfect codes in direct products of two and three cycles.  _Information Processing Letters_ , 94(1):1–6, 2005.  10.1016/j.ipl.2004.12.010.  URL https://www.scopus.com/inward/record.uri?eid=2-s2.0-13844320862&partnerID=40&md5=89fbf92310b578653cba376d19e55152.  cited By 9.
  * Klavžar et al. (2006) S. Klavžar, S. Špacapan, and J. Žerovnik.  An almost complete description of perfect codes in direct products of cycles.  _Advances in Applied Mathematics_ , 37(1):2–18, 2006.  10.1016/j.aam.2005.10.002.  URL https://www.scopus.com/inward/record.uri?eid=2-s2.0-33747517241&partnerID=40&md5=3c94149a146d61686b6c1ec8eadb4966.  cited By 10.
  * Klostermeyer and Goldwasser (2006) W. F. Klostermeyer and J. L. Goldwasser.  Total perfect codes in grid graphs.  _Bulletin of the Institute of Combinatorics and its Applications_ , 46:61–68, 2006.
  * Kratochvíl (1986) J. Kratochvíl.  Perfect codes over graphs.  _Journal of Combinatorial Theory, Series B_ , 40(2):224–228, 1986.  10.1016/0095-8956(86)90079-1.  URL https://www.scopus.com/inward/record.uri?eid=2-s2.0-38249041657&partnerID=40&md5=2277578e6b20a40d30f0cc7df684f1e2.  cited By 22.
  * Kuziak et al. (2014a) D. Kuziak, I. Peterin, and I. G. Yero.  Erratum to total domination number of cartesian products (math. commun., (2004), 9, (35-44)).  _Mathematical Communications_ , 19(1):195–200, 2014a.  URL https://www.scopus.com/inward/record.uri?eid=2-s2.0-84901670740&partnerID=40&md5=e2d066c64507f6647a970ddbe9f7e099.  cited By 0.
  * Kuziak et al. (2014b) D. Kuziak, I. Peterin, and I. G. Yero.  Efficient open domination in graph products.  _Discrete Mathematics and Theoretical Computer Science_ , 16(1):105–120, 2014b.  URL https://www.scopus.com/inward/record.uri?eid=2-s2.0-84897524357&partnerID=40&md5=cea04540aeb67f59c795b0accce3e554.  cited By 1.
  * McRae (1984) A. McRae.  _Generalizing NP-completeness Proofs for Bipartite Graphs and Chordal Graphs_.  Ph.D. Thesis, Clemson University, 1984.
  * Mekiš (2010) G. Mekiš.  Lower bounds for the domination number and the total domination number of direct product graphs.  _Discrete Mathematics_ , 310(23):3310–3317, 2010\.  10.1016/j.disc.2010.07.015.  URL https://www.scopus.com/inward/record.uri?eid=2-s2.0-77957272000&partnerID=40&md5=4fb2bbb3709c58f2e2028605439b2216.  cited By 6.
  * Rall (2005) D. F. Rall.  Total domination in categorical products of graphs.  _Discussiones Mathematicae Graph Theory_ , 25:35–44, 2005\.
  * Tamizh Chelvam and Mutharasu (2012) T. Tamizh Chelvam and S. Mutharasu.  Efficient open domination in cayley graphs.  _Applied Mathematics Letters_ , 25(10):1560–1564, 2012.  10.1016/j.aml.2011.12.036.  URL https://www.scopus.com/inward/record.uri?eid=2-s2.0-84862994859&partnerID=40&md5=588296b0e0e5cf53c720746ea1bcdb98.  cited By 5.