Supereulerian Digraph Strong Products

Hongjian Lai¹, Omaema Lasfar¹, Juan Liu²

¹Department of Mathematics, West Virginia University, Morgantown, USA.
²College of Big Data Statistics, Guizhou University of Finance and Economics, Guiyang, China.

DOI: 10.4236/am.2021.124026                

Abstract

A vertex cycle cover of a digraph H is a collection C = {C₁, C₂, …, C_k} of directed cycles in H such that these directed cycles together cover all vertices in H and such that the arc sets of these directed cycles induce a connected subdigraph of H. A subdigraph F of a digraph D is a circulation if for every vertex in F, the indegree of v equals its out degree, and a spanning circulation if F is a cycle factor. Define f (D) to be the smallest cardinality of a vertex cycle cover of the digraph obtained from D by contracting all arcs in F, among all circulations F of D. Adigraph D is supereulerian if D has a spanning connected circulation. In [International Journal of Engineering Science Invention, 8 (2019) 12-19], it is proved that if D₁ and D₂ are nontrivial strong digraphs such that D₁ is supereulerian and D₂ has a cycle vertex cover C’ with |C’| ≤ |V (D₁)|, then the Cartesian product D₁ and D₂ is also supereulerian. In this paper, we prove that for strong digraphs D₁ and D₂, if for some cycle factor F₁ of D₁, the digraph formed from D₁ by contracting arcs in F1 is hamiltonian with f (D₂) not bigger than |V (D₁)|, then the strong product D₁ and D₂ is supereulerian.

Keywords

Supereulerian Digraph, Direct Product, Strong Product, Cycle Factors, Eulerian Digraph

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 $D=\left(V\left(D\right),A\left(D\right)\right)$ with $V\left(D\right)$ and $A\left(D\right)$ denoting the vertex set and arc set of D, respectively. As we are to discuss products, for digraphs D₁ and D₂ with $u\in V\left(D_1\right)$ and $v\in V\left(D_2\right)$, we save the notation $\left(u,v\right)$ for a vertex in the product of D₁ and D₂. Thus, throughout this article, for vertices $u,v\in V\left(D\right)$ of a digraph D, we use the notation $uv$ to denote the arc oriented from $u$ to $v$ in D, where $u$ is the tail and $v$ is a head of the arc, and use $\left[u,v\right]$ to denote either $u,v$ or $\left(v,u\right)$. When $\left[u,v\right]\in A\left(D\right)$, we say that $u$ and $v$ 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 $G\left(D\right)$ to denote the underlying undirected graph of D, obtained from D by erasing all orientation on the arcs of D.

For a positive integer $n$, we define $\left[n\right]=\left\{1,2,\cdots ,n\right\}$. 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 $W=x_1,a_1,x_2,\cdots ,x_{k-1},a_{k-1},x_k$ of vertices $x_i$ and arcs $a_j$ from D such that $a_j=x_j{x}_{j+1}$ for every $i\in \left[k\right]$ and $j\in \left[k-1\right]$. A walk W is closed if $x_1=x_k$, and is open otherwise. We use $V\left(W\right)=\left\{x_i:i\in \left[k\right]\right\}$ and $A\left(W\right)=\left\{a_j:j\in \left[k-1\right]\right\}$. We say that W is a walk from $x_1$ to $x_k$ or an $\left(x_1,x_k\right)$ -walk. If $x_1=x_k$, then we say that the vertex $x_1$ is the initial vertex of W, the vertex $x_k$ is the terminal vertex of W, and $x_1$ and $x_k$ 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 $x_1{x}_2\cdots x_k$. 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 $x_1{x}_2\cdots x_{k-1}$ of the path W are distinct satisfying $k\ge 3$ and $x_1=x_k$, then W is a cycle.

A digraph D is strong if, for every pair $x,y$ of distinct vertices in D, there exists an $\left(x,y\right)$ -walk and a $\left(y,x\right)$ -walk; and is connected if $G\left(D\right)$ is connected. For the digraphs H and D, by $H\subset D$ we mean that H is a subdigraph of D. Following [3] , for a digraph D with $X,Y\subset V\left(D\right)$, define

${\left(X,Y\right)}_D=\left\{xy\in A\left(D\right):x\in X,y\in Y\right\}$.

when $Y=V\left(D\right)-X$, we define

${\partial }_D^{+}\left(X\right)={\left(X,Y\right)}_D$ and ${\partial }_D^{-}\left(X\right)={\left(Y,X\right)}_D$

For a vertex v in D, $d_D^{+}\left(v\right)=\left|{\partial }_D^{+}\left\{v\right\}\right|$ and $d_D^{-}\left(v\right)=\left|{\partial }_D^{-}\left\{v\right\}\right|$ are the out-degree and the in-degree of v in D, respectively. We use the following notation:

$N_D^{+}\left(v\right)=\left\{u\in V\left(D\right)-v:vu\in A\left(D\right)\right\}$ and $N_D^{-}\left(v\right)=\left\{w\in V\left(D\right)-v:wv\in A\left(D\right)\right\}$

The sets $N_D^{+}\left(v\right),N_D^{-}\left(v\right)$ and $N_D\left(v\right)=N_D^{+}\left(v\right)+N_D^{-}\left(v\right)$ are called the out- neighbourhood, in-neighbourhood and neighbourhood of $v$. We called the vertices in $N_D^{+}\left(v\right)$, $N_D^{-}\left(v\right)$ and $N_D\left(v\right)$ the out-neighbours, in-neighbours and neighbours of v.

Let D be a digraph. We define D to be a circulation if for any $v\in V\left(D\right)$ we have $d_D^{+}\left(v\right)=d_D^{-}\left(v\right)$ ; and a strong digraph D is eulerian if for any $v\in V\left(D\right)$, $d_D^{+}\left(v\right)=d_D^{-}\left(v\right)$. 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 $f\left(D\right)=\min \{k:D$ 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 $D_1=\left(V_1,A_1\right)$ and $D_2=\left(V_2,A_2\right)$ be two digraphs,

$V_1=\left\{u_1,u_2,\cdots ,u_{n_1}\right\}$, $V_2=\left\{v_1,v,\cdots ,v_{n_2}\right\}$ (1)

Then the Cartesian product, the Direct product and the Strong product of $D_1$ and $D_2$ are defined as following,

(i) The Cartesian product denoted by $D_1⊡D_2$ is the digraph with vertex set $V_1\times V_2$ and

$\begin{array}{l}A\left(D_1⊡D_2\right)=\{\left(\left(u_i,v_j\right),\left(u_s,v_t\right)\right):u_i=u_s\text{and}{v}_j{v}_t\in A_2\\ \text{or}{u}_i{u}_s\in A_1\text{and}{v}_j=v_t\}.\end{array}$

(ii) The Direct product denoted by $D_1\times D_2$ is the digraph with vertex set $V_1\times V_2$ and

$A\left(D_1\times D_2\right)=\left\{\left(\left(u_i,v_j\right),\left(u_s,v_t\right)\right):u_i{u}_s\in A_1\text{and}{v}_j{v}_t\in A_2\right\}.$

(iii) The Strong product denoted by $D_1⊠D_2$ is the digraph with vertex set $V_1\times V_2$ and

$\begin{array}{l}A\left(D_1⊠D_2\right)=\{\left(\left(u_i,v_j\right),\left(u_s,v_t\right)\right):u_i=u_s\text{and}{v}_j{v}_t\in A_2\text{or}{u}_i{u}_s\in A_1\\ \text{and}{v}_j=v_t\text{orboth}{u}_i{u}_s\in A_1\text{and}{v}_j{v}_t\in A_2\}.\end{array}$

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, $C_1,C_2,\cdots ,C_k$ be eulerian subdigraphs of D and set $\mathcal{F}=\left\{C_1,C_2,\cdots ,C_k\right\}$ where $k>0$ is an integer.

(i) $\mathcal{F}$ is called a cycle vertex cover of D, if each $C_i$ in $\mathcal{F}$ is a cycle, and both (i-1) and (i-2) hold:

(i-1) $V\left(D\right)={\displaystyle {\cup }_{C_i\in \mathcal{F}}V\left(C_i\right)}$.

(i-2) $F={\displaystyle {\cup }_{C_i\in \mathcal{F}}{C}_i}$ is weakly connected.

(ii) For any $u,v\in V\left(D\right)$, $\mathcal{F}$ is called an eulerian chain joining u and v, if each of the following holds.

(ii-1) $u\in V\left(C_1\right)$ and $v\in V\left(C_k\right)$.

(ii-2) $V\left(C_i\right)\cap V\left(C_{i+1}\right)\ne \varnothing$ for any i with $1\le i\le k-1$.

A subdigraphF of a digraph D is a circulation if $d_F^{-}\left(v\right)=d_F^{+}\left(v\right)>0$ holds for every $v\in V\left(F\right)$, and a spanning circulation of D is a cycle factor of D.

Let $e=\left[v_1,v_2\right]\in A\left(D\right)$ denote an arc of D which is either $v_1{v}_2$ or $v_2{v}_1$. Define D/e to be the digraph obtained from $D-e$ by identifying $v_1$ and $v_2$ into a new vertex $v_e$, and deleting the possible resulting loop(s). If $W\subseteq A\left(D\right)$ is a symmetric arc subset, then define the contraction D/W to be the digraph obtained from D by contracting each arc $e\in W$, 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 $A\left(D/W\right)\subseteq A\left(D\right)-W$. If H is a subdigraph of D, then we often use D/H for $D/A\left(H\right)$. If L is a connected symmetric component of H and $v_L$ is the vertex in D/H onto which L is contracted, then L is the contraction preimage of $v_L$. We adopt the convention to define $D/\varnothing =D$, and define a vertex $v\in V\left(D/W\right)$ 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 $A\left(F\right)$. For any circulation F of D, define

(i) $f_{D\left(F\right)}=\min \left\{\left|\mathcal{C}\right|:\mathcal{C}\text{isacyclevertexcoverof}D/F\right\}$ and,

(ii) $f\left(D\right)=\min \left\{f_{D\left(F\right)}:F\text{isacirculationof}D\right\}$.

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 D₁ and D₂ be nontrivial strong digraphs.

(i) (Xu [26] ) If D₁ and D₂ are eulerian digraphs. Then the Cartesian product $D_1⊡D_2$ is eulerian.

(ii) (Alsatami, Liu, and Zhang [17] ) If such that D₁ is supereulerian and D₂ has a cycle vertex cover ${\mathcal{C}}^{\prime }$ with $\left|{\mathcal{C}}^{\prime }\right|\le \left|V\left(D_1\right)\right|$, then the Cartesian product $D_1⊡D_2$ is supereulerian.

The current research is motivated by Problem 6 of [25] and Theorem 1.5. We prove the following.

Theorem 1.6. Let D₁ and D₂ be strong digraphs. If $f\left(D_2\right)\le \left|V\left(D_1\right)\right|$ and if for some cycle factor F of D₁, $D_1/F$ is hamiltonian, then the strong product $D_1⊠D_2$ 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 $k\ge 0$ be an integer. We use ${\mathbb{Z}}_k=\left\{1,2,\cdots ,k\right\}$ to denote the cyclic group of order k and with the additive binary operation ${+}_k$ and with k being the additive identity in ${\mathbb{Z}}_k$. Let H and $H^{\prime }$ denote two digraphs. Define $H\cup H^{\prime }$ to be the digraph with $V\left(H\cup H^{\prime }\right)=V\left(H\right)\cup V\left(H^{\prime }\right)$ and $A\left(H\cup H^{\prime }\right)=A\left(H\right)\cup A\left(H^{\prime }\right)$.

Let $T=v_1{v}_2\cdots v_k$ denote a trail. We use $T\left[v_1,v_k\right]$ to emphasize that T is oriented from $v_1$ to $v_k$. For any $1\le i\le j\le k$, we use $T\left[v_i,v_j\right]=v_i{v}_{i+1}\cdots v_{j-1}{v}_j$ to denote the sub-trail of T. Likewise, if $Q=u_1{u}_2\cdots u_k{u}_1$ is a closed trail, then for any $i,j$ with $1\le i<j\le k$, $Q\left[u_i,u_j\right]$ denotes the sub-trail $u_i{u}_{i+1}\cdots u_{j-1}{u}_j$. If $T^{\prime }=w_1{w}_2\cdots w_{k^{\prime }}$ is a trail with $v_k=w_1$ and $V\left(T\right)\cap V\left(T^{\prime }\right)=\left\{v_k\right\}$, then we use $T{T}^{\prime }$ or $T\left[v_1,v_k\right]T^{\prime }\left[v_k,w_{k^{\prime }}\right]$ to denote the trail $v_1{v}_2\cdots v_k{w}_2\cdots w_{k^{\prime }}$. If $V\left(T\right)\cap V\left(T^{\prime }\right)=\varnothing$ and there is a path $z_1{z}_2\cdots z_t$ with $z_2,\cdots ,z_{t-1}\notin V\left(T\right)\cup V\left(T^{\prime }\right)$ and with $z_1=v_k$ and $z_t=w_1$, then we use $T{z}_1\cdots z_t{T}^{\prime }$ to denote the trail $v_1{v}_2\cdots v_k{z}_2\cdots z_t{w}_2\cdots w_{k^{\prime }}$. In particular, if T is a $\left(v,w\right)$ -trail of a digraph D and $uv,wz\in A\left(D\right)-A\left(T\right)$, then we use $uvTwz$ to denote the $\left(u,z\right)$ -trail $D\left[A\left(T\right)\cup \left\{uv,wz\right\}\right]$. The subdigraphs $uvT$ and $Twz$ are similarly defined.

Lemma 2.1. Let $J_1,J_2,\cdots ,J_k$ be vertex disjoint strong subdigraphs of a digraph D, and $J={\displaystyle {\cup }_{i=1}^k{J}_i}$ is the disjoint union of these subdigraphs. Let $v_1,v_2,\cdots ,v_k$ be vertices in $V\left(D/J\right)$ such that for each $i\in \left[k\right]$, $J_i$ is the preimage of $v_i$. Suppose that $C^{\prime }=v_{i_1},v_{i_2},\cdots ,v_{i_s}$ be a cycle of D/J. Each of the following holds.

(i) D has a cycleC with $A\left(C^{\prime }\right)\subseteq A\left(C\right)$ such that for each $i\in \left[k\right]$, $V\left(C\right)\cap V\left(J_i\right)\ne \varnothing$. (Such a cycle C is called a lift of the cycle $C^{\prime }$.)

(ii) If for each $i\in {\mathbb{Z}}_s$, $e_i={v^{″}}_i{v^{\prime }}_{i+1}\in A\left(C^{\prime }\right)$ is an arc in D with ${v^{″}}_i\in V\left(J_i\right)$ and ${v^{\prime }}_{i+1}\in V\left(J_{i+1}\right)$, then $C\left[{v^{\prime }}_i,{v^{″}}_i\right]$ is a path in $J_i$.

Proof. As (i) implies (ii), it suffices to prove (i). Let $C^{\prime }=v_1{v}_2\cdots v_s{v}_1$ be a cycle of D/J, and for each $i\in {\mathbb{Z}}_s$. By definition, the arc $e_i=v_i{v}_{i+1}\in A\left(C^{\prime }\right)$ is an arc in D, and so we may assume that there exist vertices ${v^{\prime }}_i,{v^{″}}_i\in V\left(J_i\right)$ such that $e_i={v^{″}}_i{v^{\prime }}_{i+1}\in A\left(D\right)$. If $J_i$ is trivial, then we have ${v^{\prime }}_i={v^{″}}_i$. Since $J_i$ is strong, $J_i$ contains a $\left({v^{\prime }}_i,{v^{″}}_i\right)$ -path $P_i$. Thus

$C:=P_1{v^{″}}_1{v^{\prime }}_2{P}_2{v^{″}}_2{v^{\prime }}_3\cdots {v^{″}}_{i-1}{v^{\prime }}_i{P}_i{v^{″}}_i{v^{\prime }}_{i+1}{P}_{i+1}\cdots {v^{″}}_{s-1}{v^{\prime }}_s{P}_s{v^{″}}_s{v^{\prime }}_1$

is a cycle of D with $C\left[{v^{\prime }}_i,{v^{″}}_i\right]$ being a path in $J_i$, for each $i\in {\mathbb{Z}}_s$. ∎

Following [2] , we define a digraph to be cyclically connected if for every pair $x,y$ of distinct vertices of D there is a sequence of cycles $C_1,C_2,\cdots ,C_k$ such that x is in $C_1$, is in $C_k$, and $C_i$ and $C_{i+1}$ have at least one common vertex for every $i\in \left[k-1\right]$. 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 H₁ and H₂ are strong subdigraphs of D with $V\left(H_1\right)\cap V\left(H_2\right)\ne \varnothing$, then $H_1\cup H_2$ 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 $u,v\in V\left(D\right)$, there exists an eulerian chain joining u and v.

Lemma 2.4. Let D₁ and D₂ be digraphs. Each of the following holds.

(i) If D₁ and D₂ are cycles, then $D_1\times D_2$ is a circulation.

(ii) If H₁ and H₂ are arc-disjoint subdigraphs of D₁, then $H_1\times D_2$ and $H_2\times D_2$ are arc-disjoint subdigraphs of $D_1\times D_2$.

(iii) If each of D₁ and D₂ has a cycle factor, then $D_1\times D_2$ has a cycle factor.

Proof. For (i), let V₁ and V₂ be the vertex sets of D₁ and D₂, respectively. It suffices to prove that for each $\left(u_i,v_j\right)\in V_1\times V_2$, $d_{D_1\times D_2}^{+}\left(\left(u_i,v_j\right)\right)=d_{D_1\times D_2}^{-}\left(\left(u_i,v_j\right)\right)$. Let $\left(u_i,v_j\right)\in V_1\times V_2$. Since D₁ and D₂ are cycles, we have $\left|N_{D_1}^{+}\left(u_i\right)\right|=\left|N_{D_1}^{-}\left(u_i\right)\right|$ and $\left|N_{D_2}^{+}\left(v_j\right)\right|=\left|N_{D_2}^{-}\left(v_j\right)\right|$. By Definition 1.2, we have the following, which implies (i).

$\begin{array}{c}{d}_{D_1\times D_2}^{+}\left(\left(u_i,v_j\right)\right)=\left|N_{D_1\times D_2}^{+}\left(\left(u_i,v_j\right)\right)\right|\\ =\left|\left\{\left(u_s,v_t\right)\in V_1\times V_2:\left(u_i,v_j\right)\left(u_s,v_t\right)\in A\left(D_1\times D_2\right)\right\}\right|\\ =\left|\left\{\left(u_s,v_t\right)\in V_1\times V_2:u_i{u}_s\in A\left(D_1\right)\text{and}{v}_j{v}_t\in A\left(D_2\right)\right\}\right|\\ =\underset{u_s\in N_{D_1}^{+}\left(u_i\right)}{{\displaystyle \sum }}\underset{v_t\in N_{D_2}^{+}\left(v_j\right)}{{\displaystyle \sum }}\left|\left\{\left(u_s,v_t\right)\in V_1\times V_2\right\}\right|\\ =\left|N_{D_1}^{+}\left(u_i\right)\right|\cdot \left|N_{D_2}^{+}\left(v_j\right)\right|=\left|N_{D_1}^{-}\left(u_i\right)\right|\cdot \left|N_{D_2}^{-}\left(v_j\right)\right|\end{array}$

$\begin{array}{l}=\underset{u_s\in N_{D_1}^{-}\left(u_i\right)}{{\displaystyle \sum }}\underset{v_t\in N_{D_2}^{-}\left(v_j\right)}{{\displaystyle \sum }}\left|\left\{\left(u_s,v_t\right)\in V_1\times V_2\right\}\right|\\ =\left|\left\{\left(u_s,v_t\right)\in V_1\times V_2:u_s{u}_i\in A\left(D_1\right)\text{and}{v}_t{v}_j\in A\left(D_2\right)\right\}\right|\\ =\left|N_{D_1\times D_2}^{-}\left(\left(u_i,v_j\right)\right)\right|\\ =\left|\left\{\left(u_s,v_t\right)\in V_1\times V_2:\left(u_s,v_t\right)\left(u_i,v_j\right)\in A\left(D_1\times D_2\right)\right\}\right|\\ =d_{D_1\times D_2}^{-}\left(\left(u_i,v_j\right)\right)\end{array}$

To prove (ii), let H₁ and H₂ be an arc-disjoint subdigraph of D₁. If there exists an arc

$\left(u_i,v_j\right)\left(u_s,v_t\right)\in A\left(H_1\times D_2\right)\cap A\left(H_2\times D_2\right)$,

then by Definition 1.2, we must have $u_i{u}_s\in H_1\cap H_2$. Hence if H₁ and H₂ are arc-disjoint subdigraphs of D₁, then $H_1\times D_2$ and $H_2\times D_2$ are arc disjoint subdigraphs of $D_1\times D_2$.

To prove (iii), let F₁ and F₂ be the spanning circulations of D₁ and D₂, respectively. By Definition 1.2, $F_1\times F_2$ is spanning subdigraph of $D_1\times D_2$. By (i), $F_1\times F_2$ is a circulation, and so $F_1\times F_2$ is the spanning circulation of $D_1\times D_2$. Thus $F_1\times F_2$ is a cycle factor of $D_1\times D_2$. ∎

Lemma 2.5. Let D₁, D₂ be digraphs and F be a subdigraph of D₁. Then $A\left(F⊡D_2\right)\cap A\left(F\times D_2\right)=\varnothing$.

Proof. Suppose that there exists an arc $\left(u_i,v_j\right)\left(u_s,v_t\right)\in A\left(F⊡D_2\right)\cap A\left(F\times D_2\right)$. By Definition 1.2 (i), as $\left(u_i,v_j\right)\left(u_s,v_t\right)\in A\left(F⊡D_2\right)$, we have either $u_i=u_s$ and $v_j{v}_t\in A\left(D_2\right)$ or

$u_i{u}_s\in A\left(F\right)$ and $v_j=v_t$. By Definition 1.2 (ii), if $u_i=u_s$ or if $v_j=v_t$, then $\left(u_i,v_j\right)\left(u_s,v_t\right)\notin A\left(F\times D_2\right)$. It follows that $A\left(F⊡D_2\right)\cap A\left(F\times D_2\right)=\varnothing$. ∎

Theorem 2.6. (Hammack, Theorem 10.3.2 of [24] ) Let $m$ and $n$ be integers with $m\ge n\ge 2$ and let $C_m$ and $C_n$ denote the cycles of order m and n, respectively. Let $gcd\left(m,n\right)$ and $lcm\left(m,n\right)$ be the greatest common divisor and the least common multiplier of m and n, respectively. Then the direct product $C_m\times C_n$ is a vertex disjoint union of $gcm\left(m,n\right)$ cycles, each of which has length $lcm\left(m,n\right)$.

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 D₁ and D₂ be digraphs with vertex set notation in (1).

(i) Suppose that D₁ and D₂ are cycles and $v\in V\left(D_2\right)$ is an arbitrarily given vertex. Then for any cycle C in $D_1\times D_2$, there exists a vertex $u\in V\left(D_1\right)$ such that the vertex $\left(u,v\right)\in V\left(C\right)$.

(ii) Suppose that D₁ and D₂ are circulations and $v\in V\left(D_2\right)$ is an arbitrarily given vertex. Then $D_1\times D_2$ is also a circulation. Moreover, for any eulerian subdigraph F in $D_1\times D_2$, there exists a vertex $u\in V\left(D_1\right)$ such that the vertex $\left(u,v\right)\in V\left(F\right)$.

Proof. Suppose $D_1=u_1{u}_2\cdots u_{n_1}{u}_1$ and $D_2=v_1{v}_2\cdots v_{n_2}{v}_1$ are cycles, and by symmetry, assume that $v=v_1$. Let C be a cycle in $D_1\times D_2$. Thus C contains a vertex $\left(u_i,v_j\right)$. It follows by Definition 1.2 that

$C=\cdots \left(u_i,v_j\right)\left(u_{i+1},v_{j+1}\right)\cdots \left(u_{i+n_2-j},v_{n_2}\right)\left(u_{i+n_2-j+1},v_1\right)\cdots$

where the subscripts of vertices in D₁ are taken in ${\mathbb{Z}}_{n_1}$ and those of vertices in D₂ are taken in ${\mathbb{Z}}_{n_2}$. It follows that $u=u_{i+n_2-j+1}$. This proves (i). Suppose that D₁ and D₂ are circulations. By (2), each of D₁ and D₂ is an arc-disjoint union of cycles. By Lemma 2.4, $D_1\times D_2$ is also a circulation. Let F be an eulerian subdigraph in $D_1\times D_2$. By (2), F is also an arc-disjoint union of cycles $C_1,C_2,\cdots$. Applying Lemma 2.7 (i) to each cycle $C_i$, we conclude that (ii) holds as well. ∎

3. Proofs of Theorem 1.6

Assume that D₁ and D₂ are two strong digraphs, and for some cycle factor F of D₁, D₁/F is hamiltonian with $f\left(D_2\right)\le \left|V\left(D_1\right)\right|$. We start with some notation for the copies of factors in the Cartesian product.

Definition 3.1. Let $D_1=\left(V_1,A_1\right)$ and $D_2=\left(V_2,A_2\right)$ be two strong digraphs with $V_1=\left\{u_1,u_2,\cdots ,u_{n_1}\right\}$ and $V_2=\left\{v_1,v_2,\cdots ,v_{n_2}\right\}$. For $i\in \left\{1,2\right\}$, let $H_i$ be a subdigraph of $D_i$.

(i) For each $u\in V_1$, let $D_2^u$ be the subdigraph of $D_1⊡D_2$ induced by $V\left(D_2^u\right)=\left\{\left(u,v_i\right):1\le i\le n_2\right\}$. The subdigraph $D_2^u$ is called the u-copy of D₂ in $D_1⊡D_2$.

(ii) For each $v\in V_2$, let $D_1^v$ be the subdigraph of $D_1⊡D_2$ induced by $V\left(D_1^v\right)=\left\{\left(u_i,v\right):1\le i\le n_1\right\}$. The subdigraph $D_1^v$ is called the v-copy of D₁ in $D_1⊡D_2$.

(iii) More generally, for each $u\in V_1$ (or $v\in V_2$, respectively), let $H_2^u$ (or $H_1^v$, respectively) be the subdigraph of $D_2^u$ (or $D_1^v$, respectively) induced by $A\left(H_2^u\right)=\left\{\left(u,v_i\right)\left(u,{v^{\prime }}_i\right):v_i{v^{\prime }}_i\in A\left(H_2\right)\right\}$ (or $A\left(H_1^v\right)=\left\{\left(u_i,v\right)\left({u^{\prime }}_i,v\right):u_i{u^{\prime }}_i\in A\left(H_1\right)\right\}$, respectively). The subdigraph $H_1^v$ is called the v-copy of H₁ in $D_1⊡D_2$ and the subdigraph $H_2^u$ is called the u-copy of H₂ in $D_1⊡D_2$.

If two digraphs D and H are isomorphic, then we write $D\cong H$. The following is an immediate observation from Definition 3.1 for the Cartesian product $D_1⊡D_2$ of two digraphs D₁ and D₂.

For any $v\in V\left(D_2\right)$, $D_1\cong D_1^v$, and for any $u\in V\left(D_1\right)$, $D_2\cong D_2^u$. (3)

Let F be a cycle factor of D₁ such that D₁/F has a Hamilton cycle. Since F is a cycle factor of D₁, each component of F is an eulerian subdigraph of D₁. Let

$F_1,F_2,\cdots ,F_k$ be the components of F, and $J=D_1/F$. (4)

Then $V\left(J\right)=\left\{w_1,w_2,\cdots ,w_k\right\}$, where for each $i\in \left[k\right]$, $w_i$ is the contraction image in J of the eulerian subdigraph $F_i$ in D₁. SinceJ is hamiltonian, we may by symmetry assume that $C^{\prime }=w_1{w}_2\cdots w_k{w}_1$ is a hamilton cycle ofJ. It follows by Lemma 2.1 that

D₁ has a cycle C with $A\left(C^{\prime }\right)\subseteq A\left(C\right)$. (5)

Now we consider D₂. Let $f\left(D_2\right)=m\le \left|V\left(D_1\right)\right|$ and $F^{\prime }$ be a circulation of D₂ such that $D_2/F^{\prime }$ has a cycle vertex cover ${\mathcal{C}}^{\prime }=\left\{{C^{\prime }}_1,{C^{\prime }}_2,\cdots ,{C^{\prime }}_m\right\}$. Let ${F^{\prime }}_1,{F^{\prime }}_2,\cdots ,{F^{\prime }}_{k^{\prime }}$ be the components of $F^{\prime }$, ${w^{\prime }}_{k^{\prime }+1},\cdots ,{w^{\prime }}_t$ be the vertices in $V\left(D_2\right)-V\left(F^{\prime }\right)$. We define, for each i with $k^{\prime }+1\le i\le t$, ${F^{\prime }}_i$ to be the digraph with $V\left({F^{\prime }}_i\right)=\left\{{w^{\prime }}_i\right\}$ and $A\left({F^{\prime }}_i\right)=\varnothing$. With these definitions, we have

$V\left(D_2/F^{\prime }\right)=\left\{{w^{\prime }}_1,{w^{\prime }}_2,\cdots ,{w^{\prime }}_{k^{\prime }},{w^{\prime }}_{k^{\prime }+1},\cdots ,{w^{\prime }}_t\right\}$ (6)

By Lemma 2.1, for each $j\in \left[m\right]$, ${C^{\prime }}_j$ in ${\mathcal{C}}^{\prime }$ can be lifted to a cycle $C_j$ in $D_2$. To construct a spanning eulerian subdigraph of $D_1⊠D_2$, we start by justifying the following claims.

Claim 1. Each of the following holds.

(i) For any $i\in \left[k\right]$, and $j\in \left[t\right]$, $F_i\times {F^{\prime }}_j$ is a circulation.

(ii) For any $i\in \left[k\right]$, and $j\in \left[t\right]$, $F_i⊡{F^{\prime }}_j$ is an eulerian digraph.

(iii) For any $i\in \left[k\right]$, and for each $j\in \left[t\right]$, if $v\in V\left({F^{\prime }}_j\right)$, then $F_i^v\cup \left(F_i\times {F^{\prime }}_j\right)$ is a spanning eulerian subdigraph $F_i⊠{F^{\prime }}_j$.

Proof. For each $i\in \left[k\right]$, $F_i$ is an eulerian subdigraph of $D_1$, so $F_i$ is a disjoint union of cycles. Similarly, for each $j\in \left[k^{\prime }\right]$, ${F^{\prime }}_j$ is an eulerian sudigraph of $D_2$, so ${F^{\prime }}_j$ is a disjoint union of cycles. By Lemma 2.7, $F_i\times {F^{\prime }}_j$ is a circulation.

By assumption, for each $i\in \left[k\right]$, $F_i$ is an eulerian subdigraph of $D_1$. If $j\in \left[k^{\prime }\right]$, then as ${F^{\prime }}_j$ is an eulerian sudigraph of $D_2$, it follows by Theorem 1.5 (i) that $F_i⊡{F^{\prime }}_j$ is an eulerian digraph.

Now assume that $k^{\prime }+1\le j\le t$. Then $V\left({F^{\prime }}_j\right)=\left\{{w^{\prime }}_j\right\}$, and so by (3), $F_i⊡{F^{\prime }}_j=F_i^{{w^{\prime }}_j}\cong F_i$ is eulerian. This proves (ii).

For each $i\in \left[k\right]$, each $j\in \left[t\right]$ and a fixed vertex $v\in V\left({F^{\prime }}_j\right)$, let $J^{\prime }=F_i^v\cup \left(F_i\times {F^{\prime }}_j\right)$. By (i), $F_i\times {F^{\prime }}_j$ is a circulation. By (3), $F_i^v\cong F_i$ is an eulerian digraph. By Lemma 2.5, $A\left(F_i^v\right)\cap A\left(F_i\times {F^{\prime }}_j\right)=\varnothing$. It follows that for any vertex $z\in V\left(J\right)$,

$d_J^{+}\left(z\right)=d_{F_i^v}^{+}\left(z\right)+d_{F_i\times {F^{\prime }}_j}^{+}\left(z\right)=d_{F_i^v}^{-}\left(z\right)+d_{F_i\times {F^{\prime }}_j}^{-}\left(z\right)=d_J^{-}(\; z\; )$

and so $J^{\prime }$ is a circulation. Without loss of generality, we denote $V\left(F_i\right)=\left\{u_{i_1},u_{i_2},\cdots ,u_{i_{t_i}}\right\}$ and $V\left({F^{\prime }}_j\right)=\left\{v_{j_1},v_{j_2},\cdots ,v_{j_{s_j}}\right\}$ with $v=v_{j_1}$. To prove that $J^{\prime }$ is connected, let $z_0=\left(u_{i_1},v_{j_1}\right)\in V\left(J^{\prime }\right)$ and let $J_1$ be the connected component of $J^{\prime }$ that contains $z_0$. If $J^{\prime }$ is not connected, then by symmetry, we may assume that there exists a vertex $\left(u_{i_2},v_{j_2}\right)\in V\left(J^{\prime }\right)-V\left(J_1\right)$. As $F_i\times {F^{\prime }}_j$ is a circulation, there must be an eulerian subdigraph F of $F_i\times {F^{\prime }}_j$ with

$\left(u_{i_2},v_{j_2}\right)\in V\left(F\right)$. By Lemma 2.7 (ii), there exists a vertex $u^{\prime }\in V\left(D_1\right)$ such that $\left(u^{\prime },v_{j_1}\right)\in V\left(F\right)$. Thus by Definition 3.1 (ii), $V\left(F\right)\cap V\left(F_i^v\right)\ne \varnothing$. By (3) and (4), $F_i^v\cong F_i$ is connected, and so both $\left(u_{i_1},v_{j_1}\right)$ and $\left(u^{\prime },v_{j_1}\right)$ must be in the same component of $J^{\prime }$. This implies that $\left(u^{\prime },v_{j_1}\right)\in V\left(J_1\right)$. Since $\left(u_{i_2},v_{j_2}\right)$ and $\left(u^{\prime },v_{j_1}\right)$ are in the same component of $J^{\prime }$, It follows that $\left(u_{i_2},v_{j_2}\right)\in V\left(J_1\right)$ also, contrary to the assumption that $\left(u_{i_2},v_{j_2}\right)\in V\left(J^{\prime }\right)-V\left(J_1\right)$. Hence $J^{\prime }$ must be connected, and so $F_i^v\cup \left(F_i\times {F^{\prime }}_j\right)$ is a spanning eulerian subdigraph $F_i⊠{F^{\prime }}_j$. ∎

Claim 2. Let $C^{\prime }$ be a Hamilton cycle of J and C be a lift of $C^{\prime }$ in $D_1$ as warranted by (5). For each $v\in V\left(D_2\right)$, let $C^v$ denote the v-copy of C in $D_1⊡D_2$. For each $j\in \left[t\right]$, if $v,v^{\prime }\in V\left({F^{\prime }}_j\right)$ are two distinct vertices, then

$H_{v,v^{\prime };j}:={\displaystyle \underset{i=1}{\overset{k}{\cup }}\left(F_i^{v^{\prime }}\cup \left(F_i\times {F^{\prime }}_j\right)\right)}\cup C^v$

is a spanning eulerian subdigraph $D_1⊠{F^{\prime }}_j$.

Proof. By Lemma 2.1. for any $v\in V\left(D_2\right)$, $C^v$ has the property that for any $i\in \left[k\right]$, $V\left(C^v\right)\cap V\left(F_i^v\right)\ne \varnothing$. By Claim 1 (iii), for any $i\in \left[k\right]$ and for any $j\in \left[t\right]$, $F_i^{v^{\prime }}\cup \left(F_i\times {F^{\prime }}_j\right)$ is a spanning eulerian subdigraph $F_i⊠{F^{\prime }}_j$ and so $F_i^{v^{\prime }}\cup \left(F_i\times {F^{\prime }}_j\right)$ is a strong subdigraph of $D_1⊠{F^{\prime }}_j$. Since for any $i\in \left[k\right]$, $V\left(C^v\right)\cap V\left(F_i^v\right)\ne \varnothing$, we may assume that for some vertex $u\in V\left(F_i\right)$, $\left(u,v\right)\in V\left(C^v\right)\cap V\left(F_i^v\right)$. As $v\in V\left({F^{\prime }}_j\right)$, we have $\left(u,v\right)\in V\left(C^v\right)\cap V\left(F_i^{v^{\prime }}\cup \left(F_i\times {F^{\prime }}_j\right)\right)$ and so $F_i^{v^{\prime }}\cup \left(F_i\times {F^{\prime }}_j\right)\cup C^v$ is connected. Since $v\ne v^{\prime }$, $A\left(C^v\right)\cap A\left(F_i^{v^{\prime }}\cup \left(F_i\times {F^{\prime }}_j\right)\right)=\varnothing$, we conclude from the facts that $C^v$ and $F_i\times {F^{\prime }}_j$ are circulations (see Claim 1 (i)) that $F_i^{v^{\prime }}\cup \left(F_i\times {F^{\prime }}_j\right)\cup C^v$ is eulerian. As $i\in \left[k\right]$ is arbitrary, we conclude that

$H_{v,v^{\prime };j}:={\displaystyle \underset{i=1}{\overset{k}{\cup }}\left(F_i^{v^{\prime }}\cup \left(F_i\times {F^{\prime }}_j\right)\right)}\cup C^v$

is an eulerian subdigraph with vertex set $V\left(H_{v,v^{\prime };j}\right)={\displaystyle {\cup }_{i=1}^k\left(F_i\times {F^{\prime }}_j\right)}=V\left(D_1⊠{F^{\prime }}_j\right)$. This proves Claim 2. ∎

Claim 3 Let $u\in V\left(D_1\right)$ be an arbitrary vertex, $F^{\prime }$ be a circulation of $D_2$ such that $D_2/F^{\prime }$ has a cycle vertex cover ${\mathcal{C}}^{\prime }=\left\{{C^{\prime }}_1,{C^{\prime }}_2,\cdots ,{C^{\prime }}_m\right\}$ with $m=f\left(D_2\right)\le \left|V\left(D_1\right)\right|$. Each of the following holds.

(i) ${F^{\prime }}^u$ is a circulation of $D_2^u$.

(ii) For any $j\in \left[m\right]$, ${C^{\prime }}_j^u$ is a cycle of $D_2^u/{F^{\prime }}^u$ and $\left\{{C^{\prime }}_1^u,{C^{\prime }}_2^u,\cdots ,{C^{\prime }}_m^u\right\}$ is a cycle vertex cover of $D_2^u/{F^{\prime }}^u$.

(iii) Let $u\in V\left(D_1\right)$ be a vertex, $h\in \left[m\right]$ be arbitrarily given. For any vertex ${w^{\prime }}_j\in V\left({C^{\prime }}_h\right)$, let $v\left(j\right),v^{\prime }\left(j\right)$ be two distinct vertices in $V\left({F^{\prime }}_j\right)$, and $C_h$ be a lift of ${C^{\prime }}_h$ in $D_2$. Then

$H_h^u=\left[{\displaystyle \underset{{w^{\prime }}_j\in V\left({C^{\prime }}_h\right)}{\cup }{H}_{v\left(j\right),v^{\prime }\left(j\right);j}}\right]\cup C_h^u$

is an eulerian digraph with $V\left(H_h^u\right)={\displaystyle {\cup }_{v_j\in V\left(C_h\right)}V\left(D_1^{v_j}\right)}$.

Proof. Each of (i) and (ii) follows from (3) and the definition of ${\mathcal{C}}^{\prime }$. It remains to prove (iii). By Lemma 2.1, ${C^{\prime }}_h$ can be lifted to a cycle $C_h$ in $D_2$. For any ${w^{\prime }}_j\in V\left({C^{\prime }}_h\right)$, pick two distinct vertices $v,v^{\prime }\in V\left({F^{\prime }}_j\right)$. By Claim 2, $H_{v,v^{\prime };j}$ defined in Claim 2 is a spanning eulerian subdigraph $D_1⊠{F^{\prime }}_j$. By Lemma 2.5, $C_h^u=D_1\left[\left\{u\right\}\right]⊡C_h$ is arc-disjoint from each $H_{v,v^{\prime };j}$, and so by the facts that $C_h^u$ is a directed cycle and $H_{v,v^{\prime };j}$ is eulerian, it follows that $H_h^u$ is a circulation. By Definition 3.1 (iii) and by Lemma 2.5, ${w^{\prime }}_j\in V\left({C^{\prime }}_h\right)$ if and only if $V\left(C_h^u\right)\cap V\left({F^{\prime }}_j^u\right)\ne \varnothing$. This is equivalent to saying that a vertex ${w^{\prime }}_j\in V\left({C^{\prime }}_h\right)$ if and only if for some vertex $v^{″}\in V\left({F^{\prime }}_j\right)$ with $\left(u,v^{″}\right)\in V\left(C_h^u\right)$. Since $C_h^u$ is a cycle, and since, for each ${w^{\prime }}_j\in V\left({C^{\prime }}_h\right)$, there exists some vertex $v^{″}\in V\left({F^{\prime }}_j\right)$ with $\left(u,v^{″}\right)\in V\left(C_h^u\right)$, we obtain that $V\left(H_{v,v^{\prime };j}\right)\cap V\left(C_h^u\right)$ contains a vertex $\left(u,v^{″}\right)$, it follows that $H_h^u$ must be connected. Hence $H_h^u$ is a connected circulation, and so it must be eulerian. To complete the justification of Claim3 (iii), we note that by definition,

$V\left(C_h^u\right)\subseteq {\displaystyle \underset{{w^{\prime }}_j\in V\left({C^{\prime }}_h\right)}{\cup }V}\left(D_1⊠{F^{\prime }}_j\right).$

This, together with Claim 2, implies

$V\left(H_h^u\right)={\displaystyle \underset{{w^{\prime }}_j\in V\left({C^{\prime }}_h\right)}{\cup }\left(H_{v\left(j\right),v^{\prime }\left(j\right);j}\right)}\cup V\left(C_h^u\right)={\displaystyle \underset{{w^{\prime }}_j\in V\left({C^{\prime }}_h\right)}{\cup }V}\left(D_1⊠{F^{\prime }}_j\right)={\displaystyle \underset{v_j\in V\left(C_h\right)}{\cup }V}\left(D_1^{v_j}\right).$

This completes the proof of Claim 3. ∎

Recall that $V\left(D_1\right)=\left\{u_1,u_2,\cdots ,u_{n_1}\right\}$ with $n_1\ge m=f\left(D_2\right)$. We will complete the proof of Theorem 1.6 by proving that

$H={\displaystyle \underset{h=1}{\overset{m}{\cup }}{H}_h^{u_h}}$

is a spanning eulerian subdigraph of $D_1⊠D_2$. By Claim 3 (iii), we conclude that

$V\left(H\right)={\displaystyle \underset{j=1}{\overset{t}{\cup }}V\left(D_1⊠{F^{\prime }}_j\right)}=V\left(D_1⊠D_2\right).$

As $u_1,u_2,\cdots ,u_m$ are mutually distinct, and as ${F^{\prime }}_1,{F^{\prime }}_2,\cdots ,{F^{\prime }}_t$ are mutually vertex disjoint, we conclude that the $H_h^{u_h}$ ’s are mutually arc-disjoint. By Claim 3 (iii), each $H_h^{u_h}$ is eulerian, and so H is a circulation. It remains to show that H is connected. By Claim 3 (iii), H has a component $H^{\prime }$ that contains $H_1^{u_1}$. If $H=H^{\prime }$, then done. Assume that $V\left(H\right)-V\left(H^{\prime }\right)\ne \varnothing$.

Since $H^{\prime }$ is a component, if some $H_h^{u_h}$ contains a vertex in $H^{\prime }$, then $H^{\prime }$ contains $H_h^{u_h}$ as subdigraph. Thus every $H_h^{u_h}$ is either contained in $H^{\prime }$ or totally disjoint from $H^{\prime }$. Let $W=\left\{{w^{\prime }}_j\in V\left(D_2/F^{\prime }\right):H_j^{u_j}\text{iscontainedin}{H}^{\prime }\right\}$. Then as $H\ne H^{\prime }$, $V\left(D_2/F^{\prime }\right)-W\ne \varnothing$. Since $C^{\prime }$ is a cycle vertex cover of $D_2/F^{\prime }$, it follows by Definition 1.3 (i-2) that there must be a cycle ${C^{\prime }}_j\in {\mathcal{C}}^{\prime }$ such that ${C^{\prime }}_j$ contains a vertex $w^{\prime }\in W$ and a vertex $w^{″}\in \left(D_2/F^{\prime }\right)-W$. Since $w^{\prime }\in W$, $H_j^{u_j}$ is contained in $H^{\prime }$. Since $w^{\prime },w^{″}\in V\left({C^{\prime }}_j\right)$, it follows that $w^{″}\in W$, contrary to the fact that $w^{″}\in \left(D_2/F^{\prime }\right)-W$. This contradiction indicates that we must have $H=H^{\prime }$, and so H is a spanning eulerian subdigraph of $D_1⊠D_2$. ∎

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).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer, New York.
[2]	Bang-Jensen, J. and Gutin, G. (2010) Digraphs: Theory, Algorithms and Applications. 2nd Edition, Springer, London. https://doi.org/10.1007/978-1-84800-998-1
[3]	Veblen, O. (1912-1913) An Application of Modular Equations in Analysis Situs. Annals of Mathematics Second Series, 14, 86-94. https://doi.org/10.2307/1967604
[4]	Boesch, F.T., Suffel, C. and Tindell, R. (1977) The Spanning Subgraphs of Eulerian Graphs. Journal of Graph Theory, 1, 79-84. https://doi.org/10.1002/jgt.3190010115
[5]	Pulleyblank, W.R. (1979) A Note on Graphs Spanned by Eulerian Graphs. Journal of Graph Theory, 3, 309-310. https://doi.org/10.1002/jgt.3190030316
[6]	Catlin, P.A. (1992) Supereulerian Graphs: A Survey. Journal of Graph Theory, 16, 177-196. https://doi.org/10.1002/jgt.3190160209
[7]	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.
[8]	Lai, H.-J., Shao, Y. and Yan, H. (2013) An Update on Supereulerian Graphs. WSEAS Transactions on Mathematics, 12, 926-940.
[9]	Gutin, G. (1993) Cycles and Paths in Directed Graphs. PhD Thesis, School of Mathematics, Tel Aviv University, Tel Aviv-Yafo.
[10]	Gutin, G. (2000) Connected (g; f)-Factors and Supereulerian Digraphs. Ars Combinatoria, 54, 311-317.
[11]	Hong, Y.M., Lai, H.-J. and Liu, Q.H. (2014) Supereulerian Digraphs. Discrete Mathematics, 330, 87-95. https://doi.org/10.1016/j.disc.2014.04.018
[12]	Hong, Y.M., Liu, Q.H. and Lai, H.-J. (2016) Ore-Type Degree Condition of Supereulerian Digraphs. Discrete Mathematics, 339, 2042-2050. https://doi.org/10.1016/j.disc.2016.03.015
[13]	Bang-Jensen, J. and Maddaloni, A. (2015) Sufficient Conditions for a Digraph to Be Supereulerian. Journal of Graph Theory, 79, 8-20. https://doi.org/10.1002/jgt.21810
[14]	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. https://doi.org/10.1007/s00373-020-02229-x
[15]	Alfegari, M.J. and Lai, H.-J. (2016) Supereulerian Digraphs with Large Arc-Strong Connectivity. Journal of Graph Theory, 81, 393-402. https://doi.org/10.1002/jgt.21885
[16]	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. https://doi.org/10.1016/j.ipl.2015.12.008
[17]	Alsatami, K.A., Liu, J. and Zhang, X.D. (2019) Supereulerian and Trailable Digraph Products. International Journal of Engineering Science Invention, 8, 12-19.
[18]	Alsatami, K.A., Zhang, X.D., Liu, J. and Lai, H.-J. (2016) On a Class of Supereulerian Digraphs. Applied Mathematics, 7, 320-326. https://doi.org/10.4236/am.2016.73029
[19]	Dong, C.C., Liu, J. and Zhang, X.D. (2018) Supereulerian Digraphs with Given Diameter. Applied Mathematics and Computation, 329, 5-13. https://doi.org/10.1016/j.amc.2018.01.052
[20]	Dong, C.C. and Liu, J. (2018) Supereulerian-Extended Digraphs. Journal of Mathematical Research with Applications, 38, 111-120.
[21]	Dong, C.C., Liu, J. and Meng, J.X. (2020) Supereulerian 3-Path-Quasi-Transitive Digraphs. Applied Mathematics and Computation, 372, Article ID: 124964. https://doi.org/10.1016/j.amc.2019.124964
[22]	Liu, J., Liu, Q.H., Zhang, X.D. and Chen, X. (2021) Trail-Connected Tournaments. Applied Mathematics and Computation, 389, Article ID: 125595. https://doi.org/10.1016/j.amc.2020.125595
[23]	Zhang, X.D., Liu, J., Wang, L. and Lai, H.-J. (2018) Supereulerian Bipartite Digraphs. Journal of Graph Theory, 89, 64-75. https://doi.org/10.1002/jgt.22240
[24]	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. https://doi.org/10.1007/978-3-319-71840-8_10
[25]	Gould, R. (2003) Advances on the Hamiltonian Problem—A Survey. Graphs and Combinatorics, 19, 7-52. https://doi.org/10.1007/s00373-002-0492-x
[26]	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. https://doi.org/10.1007/978-1-4757-3387-7_3