1. Introduction
We consider finite graphs and digraphs. Undefined terms and notation will follow [1] for graphs and [2] for digraphs. We will often write
with
and
denoting the vertex set and arc set of D, respectively. As we are to discuss products, for digraphs D1 and D2 with
and
, we save the notation
for a vertex in the product of D1 and D2. Thus, throughout this article, for vertices
of a digraph D, we use the notation
to denote the arc oriented from
to
in D, where
is the tail and
is a head of the arc, and use
to denote either
or
. When
, we say that
and
are adjacent. Using the terminology in [2] , digraphs do not have parallel arcs (arcs with the same tail and the same head) or loops (arcs with same tail and head). If D is a digraph, we often use
to denote the underlying undirected graph of D, obtained from D by erasing all orientation on the arcs of D.
For a positive integer
, we define
. Throughout this paper, we use paths, cycles and trails as defined in [1] when the discussion is on an undirected graph G, and to denote directed paths, directed cycles and directed trails when the discussion is on a digraphD. A walk in D is an alternating sequence
of vertices
and arcs
from D such that
for every
and
. A walk W is closed if
, and is open otherwise. We use
and
. We say that W is a walk from
to
or an
-walk. If
, then we say that the vertex
is the initial vertex of W, the vertex
is the terminal vertex of W, and
and
are end-vertices of W. The length of a walk is the number of its arcs. When the arcs of W are understood from the context, we will denote W by
. A trail in D is a walk in which all arcs are distinct. Always we use a trail to denote an open trail. If the vertices of W are distinct, then W is a path. If the vertices
of the path W are distinct satisfying
and
, then W is a cycle.
A digraph D is strong if, for every pair
of distinct vertices in D, there exists an
-walk and a
-walk; and is connected if
is connected. For the digraphs H and D, by
we mean that H is a subdigraph of D. Following [3] , for a digraph D with
, define
.
when
, we define
and
For a vertex v in D,
and
are the out-degree and the in-degree of v in D, respectively. We use the following notation:
and
The sets
and
are called the out- neighbourhood, in-neighbourhood and neighbourhood of
. We called the vertices in
,
and
the out-neighbours, in-neighbours and neighbours of v.
Let D be a digraph. We define D to be a circulation if for any
we have
; and a strong digraph D is eulerian if for any
,
. D is eulerian if D is a connected circulation. Thus, by definition, an eulerian digraph is also a strong digraph. It is known [3] that a digraph D is a circulation if and only if D is an arc-disjoint union of cycles. A subdigraph F of D is a cycle factor of D if F is spanning circulation of D. Define
has a cycle factor with k components}. The following is well-known or immediately from the definition.
Theorem 1.1. (Euler, see Theorem 1.7.2 of [2] and Veblen [3] ) Let D be a digraph. The following are equivalent.
(i) D is eulerian.
(ii) D is a spanning closed trail.
(iii) D is a disjoint union of cycles and D is connected.
The supereulerian problem was introduced by Boesch, Suffel, and Tindell in [4] , seeking to characterize graphs that have spanning Eulerian subgraphs. Pulleyblank in [5] proved that determining whether a graph is supereulerian, even within planar graphs, is NP-complete. There have been lots of research on this topic. For more literature on supereulerian graphs, see Catlin’s informative survey [6] , as well as the later updates in [7] and [8]. The supereulerian problem in digraphs is considered by Gutin [9] [10]. A digraph D is supereulerian if D contains a spanning eulerian subdigraph, or equivalently, a connected cycle factor. Thus, supereulerian digraphs must be strong, and every hamiltonian digraph is also a supereulerian digraph.
The supereulerian digraph problem is to characterize the strong digraphs that contain a spanning closed trail.
Other than the researches on hamiltonian digraphs, a number of studies on supereulerian di-graphs have been conducted recently. In particular, Hong et al in [11] [12] and Bang-Jensen and Maddaloni [13] presented some best possible sufficient degree conditions for supereulerian digraphs. Several researches on various conditions of supereulerian digraphs can be found in [13] - [23] , among others.
Following [24] , some digraph products are defined as follows.
Definition 1.2. Let
and
be two digraphs,
,
(1)
Then the Cartesian product, the Direct product and the Strong product of
and
are defined as following,
(i) The Cartesian product denoted by
is the digraph with vertex set
and
(ii) The Direct product denoted by
is the digraph with vertex set
and
(iii) The Strong product denoted by
is the digraph with vertex set
and
It is often of interest to investigate natural conditions on the factors of a product to assure hamiltonicity of the product, as seen in Problem 6 of [25]. Researchers have investigated conditions on factors of digraph products to warrant the product to be supereulerian. Alsatami, Liu, and Zhang in [17] introduced eulerian vertex cover of a digraph D to study the supereulerian digraph problem.
Definition 1.3. Let D be a digraph,
be eulerian subdigraphs of D and set
where
is an integer.
(i)
is called a cycle vertex cover of D, if each
in
is a cycle, and both (i-1) and (i-2) hold:
(i-1)
.
(i-2)
is weakly connected.
(ii) For any
,
is called an eulerian chain joining u and v, if each of the following holds.
(ii-1)
and
.
(ii-2)
for any i with
.
A subdigraphF of a digraph D is a circulation if
holds for every
, and a spanning circulation of D is a cycle factor of D.
Let
denote an arc of D which is either
or
. Define D/e to be the digraph obtained from
by identifying
and
into a new vertex
, and deleting the possible resulting loop(s). If
is a symmetric arc subset, then define the contraction D/W to be the digraph obtained from D by contracting each arc
, and deleting any resulting loops. Thus even D does not have parallel arcs, a contraction D/W is loopless but may have parallel arcs, with
. If H is a subdigraph of D, then we often use D/H for
. If L is a connected symmetric component of H and
is the vertex in D/H onto which L is contracted, then L is the contraction preimage of
. We adopt the convention to define
, and define a vertex
to be a trivial vertex if the preimage of v is a single vertex (also denoted by v) in D. Hence, we often view trivial vertices in a contraction D/W as vertices in D.
Definition 1.4. Let F be a circulation of a digraph D and D/F denote the digraph formed from D by contracting arcs in
. For any circulation F of D, define
(i)
and,
(ii)
.
By definition, if D is a circulation, then every component of D is eulerian. By Theorem 1.1, we observe the following.
Every circulation is an arc-disjoint union of cycles. (2)
There have been some former results concerning the Cartesian products of digraphs to be eulerian and to be supereulerian.
Theorem 1.5. Let D1 and D2 be nontrivial strong digraphs.
(i) (Xu [26] ) If D1 and D2 are eulerian digraphs. Then the Cartesian product
is eulerian.
(ii) (Alsatami, Liu, and Zhang [17] ) If such that D1 is supereulerian and D2 has a cycle vertex cover
with
, then the Cartesian product
is supereulerian.
The current research is motivated by Problem 6 of [25] and Theorem 1.5. We prove the following.
Theorem 1.6. Let D1 and D2 be strong digraphs. If
and if for some cycle factor F of D1,
is hamiltonian, then the strong product
is supereulerian.
In the next section, we develop some lemmas which will be used in ourarguments. The proof of the main result will be given in the last section.
2. Lemmas
Let
be an integer. We use
to denote the cyclic group of order k and with the additive binary operation
and with k being the additive identity in
. Let H and
denote two digraphs. Define
to be the digraph with
and
.
Let
denote a trail. We use
to emphasize that T is oriented from
to
. For any
, we use
to denote the sub-trail of T. Likewise, if
is a closed trail, then for any
with
,
denotes the sub-trail
. If
is a trail with
and
, then we use
or
to denote the trail
. If
and there is a path
with
and with
and
, then we use
to denote the trail
. In particular, if T is a
-trail of a digraph D and
, then we use
to denote the
-trail
. The subdigraphs
and
are similarly defined.
Lemma 2.1. Let
be vertex disjoint strong subdigraphs of a digraph D, and
is the disjoint union of these subdigraphs. Let
be vertices in
such that for each
,
is the preimage of
. Suppose that
be a cycle of D/J. Each of the following holds.
(i) D has a cycleC with
such that for each
,
. (Such a cycle C is called a lift of the cycle
.)
(ii) If for each
,
is an arc in D with
and
, then
is a path in
.
Proof. As (i) implies (ii), it suffices to prove (i). Let
be a cycle of D/J, and for each
. By definition, the arc
is an arc in D, and so we may assume that there exist vertices
such that
. If
is trivial, then we have
. Since
is strong,
contains a
-path
. Thus
is a cycle of D with
being a path in
, for each
. ∎
Following [2] , we define a digraph to be cyclically connected if for every pair
of distinct vertices of D there is a sequence of cycles
such that x is in
, is in
, and
and
have at least one common vertex for every
. The following results are useful. Lemma 2.2 (ii) follows immediately from definition of strong digraphs.
Lemma 2.2. Let D be a digraph.
(i) (Exercise 1.17 of [2] ) A digraph D is strong if and only if it is cyclically connected.
(ii) If H1 and H2 are strong subdigraphs of D with
, then
is also strong.
Proposition 2.3. (Alsatami, Liu and Zhang, Proposition 2.1 of [17] ) Let D be a weakly connected digraph.
Then the following are equivalent.
(i) D has a cycle vertex cover.
(ii) D is strong.
(iii) D is cyclically connected.
(iv) For any vertices
, there exists an eulerian chain joining u and v.
Lemma 2.4. Let D1 and D2 be digraphs. Each of the following holds.
(i) If D1 and D2 are cycles, then
is a circulation.
(ii) If H1 and H2 are arc-disjoint subdigraphs of D1, then
and
are arc-disjoint subdigraphs of
.
(iii) If each of D1 and D2 has a cycle factor, then
has a cycle factor.
Proof. For (i), let V1 and V2 be the vertex sets of D1 and D2, respectively. It suffices to prove that for each
,
. Let
. Since D1 and D2 are cycles, we have
and
. By Definition 1.2, we have the following, which implies (i).
To prove (ii), let H1 and H2 be an arc-disjoint subdigraph of D1. If there exists an arc
,
then by Definition 1.2, we must have
. Hence if H1 and H2 are arc-disjoint subdigraphs of D1, then
and
are arc disjoint subdigraphs of
.
To prove (iii), let F1 and F2 be the spanning circulations of D1 and D2, respectively. By Definition 1.2,
is spanning subdigraph of
. By (i),
is a circulation, and so
is the spanning circulation of
. Thus
is a cycle factor of
. ∎
Lemma 2.5. Let D1, D2 be digraphs and F be a subdigraph of D1. Then
.
Proof. Suppose that there exists an arc
. By Definition 1.2 (i), as
, we have either
and
or
and
. By Definition 1.2 (ii), if
or if
, then
. It follows that
. ∎
Theorem 2.6. (Hammack, Theorem 10.3.2 of [24] ) Let
and
be integers with
and let
and
denote the cycles of order m and n, respectively. Let
and
be the greatest common divisor and the least common multiplier of m and n, respectively. Then the direct product
is a vertex disjoint union of
cycles, each of which has length
.
We can show a bit more structural properties in the direct product revealed by Theorem 2.6, which are stated in Lemma 2.7.
Lemma 2.7. Let D1 and D2 be digraphs with vertex set notation in (1).
(i) Suppose that D1 and D2 are cycles and
is an arbitrarily given vertex. Then for any cycle C in
, there exists a vertex
such that the vertex
.
(ii) Suppose that D1 and D2 are circulations and
is an arbitrarily given vertex. Then
is also a circulation. Moreover, for any eulerian subdigraph F in
, there exists a vertex
such that the vertex
.
Proof. Suppose
and
are cycles, and by symmetry, assume that
. Let C be a cycle in
. Thus C contains a vertex
. It follows by Definition 1.2 that
where the subscripts of vertices in D1 are taken in
and those of vertices in D2 are taken in
. It follows that
. This proves (i). Suppose that D1 and D2 are circulations. By (2), each of D1 and D2 is an arc-disjoint union of cycles. By Lemma 2.4,
is also a circulation. Let F be an eulerian subdigraph in
. By (2), F is also an arc-disjoint union of cycles
. Applying Lemma 2.7 (i) to each cycle
, we conclude that (ii) holds as well. ∎
3. Proofs of Theorem 1.6
Assume that D1 and D2 are two strong digraphs, and for some cycle factor F of D1, D1/F is hamiltonian with
. We start with some notation for the copies of factors in the Cartesian product.
Definition 3.1. Let
and
be two strong digraphs with
and
. For
, let
be a subdigraph of
.
(i) For each
, let
be the subdigraph of
induced by
. The subdigraph
is called the u-copy of D2 in
.
(ii) For each
, let
be the subdigraph of
induced by
. The subdigraph
is called the v-copy of D1 in
.
(iii) More generally, for each
(or
, respectively), let
(or
, respectively) be the subdigraph of
(or
, respectively) induced by
(or
, respectively). The subdigraph
is called the v-copy of H1 in
and the subdigraph
is called the u-copy of H2 in
.
If two digraphs D and H are isomorphic, then we write
. The following is an immediate observation from Definition 3.1 for the Cartesian product
of two digraphs D1 and D2.
For any
,
, and for any
,
. (3)
Let F be a cycle factor of D1 such that D1/F has a Hamilton cycle. Since F is a cycle factor of D1, each component of F is an eulerian subdigraph of D1. Let
be the components of F, and
. (4)
Then
, where for each
,
is the contraction image in J of the eulerian subdigraph
in D1. SinceJ is hamiltonian, we may by symmetry assume that
is a hamilton cycle ofJ. It follows by Lemma 2.1 that
D1 has a cycle C with
. (5)
Now we consider D2. Let
and
be a circulation of D2 such that
has a cycle vertex cover
. Let
be the components of
,
be the vertices in
. We define, for each i with
,
to be the digraph with
and
. With these definitions, we have
(6)
By Lemma 2.1, for each
,
in
can be lifted to a cycle
in
. To construct a spanning eulerian subdigraph of
, we start by justifying the following claims.
Claim 1. Each of the following holds.
(i) For any
, and
,
is a circulation.
(ii) For any
, and
,
is an eulerian digraph.
(iii) For any
, and for each
, if
, then
is a spanning eulerian subdigraph
.
Proof. For each
,
is an eulerian subdigraph of
, so
is a disjoint union of cycles. Similarly, for each
,
is an eulerian sudigraph of
, so
is a disjoint union of cycles. By Lemma 2.7,
is a circulation.
By assumption, for each
,
is an eulerian subdigraph of
. If
, then as
is an eulerian sudigraph of
, it follows by Theorem 1.5 (i) that
is an eulerian digraph.
Now assume that
. Then
, and so by (3),
is eulerian. This proves (ii).
For each
, each
and a fixed vertex
, let
. By (i),
is a circulation. By (3),
is an eulerian digraph. By Lemma 2.5,
. It follows that for any vertex
,
and so
is a circulation. Without loss of generality, we denote
and
with
. To prove that
is connected, let
and let
be the connected component of
that contains
. If
is not connected, then by symmetry, we may assume that there exists a vertex
. As
is a circulation, there must be an eulerian subdigraph F of
with
. By Lemma 2.7 (ii), there exists a vertex
such that
. Thus by Definition 3.1 (ii),
. By (3) and (4),
is connected, and so both
and
must be in the same component of
. This implies that
. Since
and
are in the same component of
, It follows that
also, contrary to the assumption that
. Hence
must be connected, and so
is a spanning eulerian subdigraph
. ∎
Claim 2. Let
be a Hamilton cycle of J and C be a lift of
in
as warranted by (5). For each
, let
denote the v-copy of C in
. For each
, if
are two distinct vertices, then
is a spanning eulerian subdigraph
.
Proof. By Lemma 2.1. for any
,
has the property that for any
,
. By Claim 1 (iii), for any
and for any
,
is a spanning eulerian subdigraph
and so
is a strong subdigraph of
. Since for any
,
, we may assume that for some vertex
,
. As
, we have
and so
is connected. Since
,
, we conclude from the facts that
and
are circulations (see Claim 1 (i)) that
is eulerian. As
is arbitrary, we conclude that
is an eulerian subdigraph with vertex set
. This proves Claim 2. ∎
Claim 3 Let
be an arbitrary vertex,
be a circulation of
such that
has a cycle vertex cover
with
. Each of the following holds.
(i)
is a circulation of
.
(ii) For any
,
is a cycle of
and
is a cycle vertex cover of
.
(iii) Let
be a vertex,
be arbitrarily given. For any vertex
, let
be two distinct vertices in
, and
be a lift of
in
. Then
is an eulerian digraph with
.
Proof. Each of (i) and (ii) follows from (3) and the definition of
. It remains to prove (iii). By Lemma 2.1,
can be lifted to a cycle
in
. For any
, pick two distinct vertices
. By Claim 2,
defined in Claim 2 is a spanning eulerian subdigraph
. By Lemma 2.5,
is arc-disjoint from each
, and so by the facts that
is a directed cycle and
is eulerian, it follows that
is a circulation. By Definition 3.1 (iii) and by Lemma 2.5,
if and only if
. This is equivalent to saying that a vertex
if and only if for some vertex
with
. Since
is a cycle, and since, for each
, there exists some vertex
with
, we obtain that
contains a vertex
, it follows that
must be connected. Hence
is a connected circulation, and so it must be eulerian. To complete the justification of Claim3 (iii), we note that by definition,
This, together with Claim 2, implies
This completes the proof of Claim 3. ∎
Recall that
with
. We will complete the proof of Theorem 1.6 by proving that
is a spanning eulerian subdigraph of
. By Claim 3 (iii), we conclude that
As
are mutually distinct, and as
are mutually vertex disjoint, we conclude that the
’s are mutually arc-disjoint. By Claim 3 (iii), each
is eulerian, and so H is a circulation. It remains to show that H is connected. By Claim 3 (iii), H has a component
that contains
. If
, then done. Assume that
.
Since
is a component, if some
contains a vertex in
, then
contains
as subdigraph. Thus every
is either contained in
or totally disjoint from
. Let
. Then as
,
. Since
is a cycle vertex cover of
, it follows by Definition 1.3 (i-2) that there must be a cycle
such that
contains a vertex
and a vertex
. Since
,
is contained in
. Since
, it follows that
, contrary to the fact that
. This contradiction indicates that we must have
, and so H is a spanning eulerian subdigraph of
. ∎
4. Concluding Remark
This research provides new conditions to ensure digraph products to be supereulerian, and adds novel knowledge to the literature of supereulerian digraph theory. Analogues to Problem 6 proposed in [25] , it would also be of interest to seek natural conditions to assure supereulerian products of digraphs. Current results in this direction in [17] and in the current research also involve certain cycle cover properties on the factor digraphs. It would be of interest to see if there exist sufficient conditions on supereulerian digraphs products that do not depend on cycle cover properties.
Acknowledgements
This research was supported by National Natural Science Foundation of China (No.11761071, 11771039, 11771443).