We consider finite graphs and digraphs. Undefined terms and notation will follow  for graphs and  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  , 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  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  , for a digraph D with , define
when , we define
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:
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  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  and Veblen  ) 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  , seeking to characterize graphs that have spanning Eulerian subgraphs. Pulleyblank in  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  , as well as the later updates in  and . The supereulerian problem in digraphs is considered by Gutin  . 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   and Bang-Jensen and Maddaloni  presented some best possible sufficient degree conditions for supereulerian digraphs. Several researches on various conditions of supereulerian digraphs can be found in  -  , among others.
Following  , some digraph products are defined as follows.
Definition 1.2. Let and be two digraphs,
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 . Researchers have investigated conditions on factors of digraph products to warrant the product to be supereulerian. Alsatami, Liu, and Zhang in  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-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
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  ) If D1 and D2 are eulerian digraphs. Then the Cartesian product is eulerian.
(ii) (Alsatami, Liu, and Zhang  ) 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  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.
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  , 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  ) 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  ) 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  ) 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
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  , it would also be of interest to seek natural conditions to assure supereulerian products of digraphs. Current results in this direction in  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.
This research was supported by National Natural Science Foundation of China (No.11761071, 11771039, 11771443).
 Chen, Z.H. and Lai, H.-J. (1995) Reduction Techniques for Super-Eulerian Graphs and Related Topics—A Survey, Combinatorics and Graph’95, Vol. 1 (Hefei). World Scientific Publishing, River Edge, NJ, 53-69.
 Algefari, M.J. and Lai, H.-J. (2021) Supereulerian Graphs with Constraints on the Matching Number and Minimum Degree. Graphs and Combinatorics, 37, 55-64.
 Algefari, M.J., Alsatami, K.A., Lai, H.-J. and Liu, J. (2016) Supereulerian Digraphs with Given Local Structures. Information Processing Letters, 116, 321-326.
 Hammack, R.H. (2018) Digraph Products. In: Bang-Jensen, J. and Gutin, G., Eds., Classes of Directed Graphs, Springer Monographs in Mathematics, Springer, Cham, 467-515.
 Xu, J.M. (2001) Topological Structure and Analysis of Interconnection Networks. In: Topological Structure and Analysis of Interconnection Networks, Vol. 7, Springer, Boston, 105-186.