Back
 AM  Vol.12 No.4 , April 2021
Supereulerian Digraph Strong Products
Abstract: A vertex cycle cover of a digraph H is a collection C = {C1, C2, …, Ck} 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 D1 and D2 are nontrivial strong digraphs such that D1 is supereulerian and D2 has a cycle vertex cover C’ with |C’| ≤ |V (D1)|, then the Cartesian product D1 and D2 is also supereulerian. In this paper, we prove that for strong digraphs D1 and D2, if for some cycle factor F1 of D1, the digraph formed from D1 by contracting arcs in F1 is hamiltonian with f (D2) not bigger than |V (D1)|, then the strong product D1 and D2 is supereulerian.

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 = ( V ( D ) , A ( D ) ) with V ( D ) and A ( D ) denoting the vertex set and arc set of D, respectively. As we are to discuss products, for digraphs D1 and D2 with u V ( D 1 ) and v V ( D 2 ) , we save the notation ( u , v ) for a vertex in the product of D1 and D2. Thus, throughout this article, for vertices u , v V ( D ) of a digraph D, we use the notation u v 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 [ u , v ] to denote either u , v or ( v , u ) . When [ u , v ] A ( D ) , 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 ( D ) 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 [ n ] = { 1 , 2 , , n } . 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 , , 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 [ k ] and j [ k 1 ] . A walk W is closed if x 1 = x k , and is open otherwise. We use V ( W ) = { x i : i [ k ] } and A ( W ) = { a j : j [ k 1 ] } . We say that W is a walk from x 1 to x k or an ( x 1 , x k ) -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 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 x k 1 of the path W are distinct satisfying k 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 ( x , y ) -walk and a ( y , x ) -walk; and is connected if G ( D ) is connected. For the digraphs H and D, by H D we mean that H is a subdigraph of D. Following [3] , for a digraph D with X , Y V ( D ) , define

( X , Y ) D = { x y A ( D ) : x X , y Y } .

when Y = V ( D ) X , we define

D + ( X ) = ( X , Y ) D and D ( X ) = ( Y , X ) D

For a vertex v in D, d D + ( v ) = | D + { v } | and d D ( v ) = | D { v } | are the out-degree and the in-degree of v in D, respectively. We use the following notation:

N D + ( v ) = { u V ( D ) v : v u A ( D ) } and N D ( v ) = { w V ( D ) v : w v A ( D ) }

The sets N D + ( v ) , N D ( v ) and N D ( v ) = N D + ( v ) + N D ( v ) are called the out- neighbourhood, in-neighbourhood and neighbourhood of v . We called the vertices in N D + ( v ) , N D ( v ) and N D ( v ) 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 V ( D ) we have d D + ( v ) = d D ( v ) ; and a strong digraph D is eulerian if for any v V ( D ) , d D + ( v ) = d D ( v ) . 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 ( D ) = 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 = ( V 1 , A 1 ) and D 2 = ( V 2 , A 2 ) be two digraphs,

V 1 = { u 1 , u 2 , , u n 1 } , V 2 = { v 1 , v , , v n 2 } (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 × V 2 and

A ( D 1 D 2 ) = { ( ( u i , v j ) , ( u s , v t ) ) : u i = u s and v j v t A 2 or u i u s A 1 and v j = v t } .

(ii) The Direct product denoted by D 1 × D 2 is the digraph with vertex set V 1 × V 2 and

A ( D 1 × D 2 ) = { ( ( u i , v j ) , ( u s , v t ) ) : u i u s A 1 and v j v t A 2 } .

(iii) The Strong product denoted by D 1 D 2 is the digraph with vertex set V 1 × V 2 and

A ( D 1 D 2 ) = { ( ( u i , v j ) , ( u s , v t ) ) : u i = u s and v j v t A 2 or u i u s A 1 and v j = v t orboth u i u s A 1 and v j v t A 2 } .

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 , , C k be eulerian subdigraphs of D and set F = { C 1 , C 2 , , C k } where k > 0 is an integer.

(i) F is called a cycle vertex cover of D, if each C i in F is a cycle, and both (i-1) and (i-2) hold:

(i-1) V ( D ) = C i F V ( C i ) .

(i-2) F = C i F C i is weakly connected.

(ii) For any u , v V ( D ) , F is called an eulerian chain joining u and v, if each of the following holds.

(ii-1) u V ( C 1 ) and v V ( C k ) .

(ii-2) V ( C i ) V ( C i + 1 ) for any i with 1 i k 1 .

A subdigraphF of a digraph D is a circulation if d F ( v ) = d F + ( v ) > 0 holds for every v V ( F ) , and a spanning circulation of D is a cycle factor of D.

Let e = [ v 1 , v 2 ] A ( D ) 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 A ( D ) is a symmetric arc subset, then define the contraction D/W to be the digraph obtained from D by contracting each arc e 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 ( D / W ) A ( D ) W . If H is a subdigraph of D, then we often use D/H for D / A ( H ) . 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 / = D , and define a vertex v V ( D / W ) 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 ( F ) . For any circulation F of D, define

(i) f D ( F ) = min { | C | : C isacyclevertexcoverof D / F } and,

(ii) f ( D ) = min { f D ( F ) : F isacirculationof D } .

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 D 1 D 2 is eulerian.

(ii) (Alsatami, Liu, and Zhang [17] ) If such that D1 is supereulerian and D2 has a cycle vertex cover C with | C | | V ( D 1 ) | , 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 D1 and D2 be strong digraphs. If f ( D 2 ) | V ( D 1 ) | and if for some cycle factor F of D1, 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 0 be an integer. We use k = { 1 , 2 , , k } to denote the cyclic group of order k and with the additive binary operation + k and with k being the additive identity in k . Let H and H denote two digraphs. Define H H to be the digraph with V ( H H ) = V ( H ) V ( H ) and A ( H H ) = A ( H ) A ( H ) .

Let T = v 1 v 2 v k denote a trail. We use T [ v 1 , v k ] to emphasize that T is oriented from v 1 to v k . For any 1 i j k , we use T [ v i , v j ] = v i v i + 1 v j 1 v j to denote the sub-trail of T. Likewise, if Q = u 1 u 2 u k u 1 is a closed trail, then for any i , j with 1 i < j k , Q [ u i , u j ] denotes the sub-trail u i u i + 1 u j 1 u j . If T = w 1 w 2 w k is a trail with v k = w 1 and V ( T ) V ( T ) = { v k } , then we use T T or T [ v 1 , v k ] T [ v k , w k ] to denote the trail v 1 v 2 v k w 2 w k . If V ( T ) V ( T ) = and there is a path z 1 z 2 z t with z 2 , , z t 1 V ( T ) V ( T ) and with z 1 = v k and z t = w 1 , then we use T z 1 z t T to denote the trail v 1 v 2 v k z 2 z t w 2 w k . In particular, if T is a ( v , w ) -trail of a digraph D and u v , w z A ( D ) A ( T ) , then we use u v T w z to denote the ( u , z ) -trail D [ A ( T ) { u v , w z } ] . The subdigraphs u v T and T w z are similarly defined.

Lemma 2.1. Let J 1 , J 2 , , J k be vertex disjoint strong subdigraphs of a digraph D, and J = i = 1 k J i is the disjoint union of these subdigraphs. Let v 1 , v 2 , , v k be vertices in V ( D / J ) such that for each i [ k ] , J i is the preimage of v i . Suppose that C = v i 1 , v i 2 , , v i s be a cycle of D/J. Each of the following holds.

(i) D has a cycleC with A ( C ) A ( C ) such that for each i [ k ] , V ( C ) V ( J i ) . (Such a cycle C is called a lift of the cycle C .)

(ii) If for each i s , e i = v i v i + 1 A ( C ) is an arc in D with v i V ( J i ) and v i + 1 V ( J i + 1 ) , then C [ v i , v i ] is a path in J i .

Proof. As (i) implies (ii), it suffices to prove (i). Let C = v 1 v 2 v s v 1 be a cycle of D/J, and for each i s . By definition, the arc e i = v i v i + 1 A ( C ) is an arc in D, and so we may assume that there exist vertices v i , v i V ( J i ) such that e i = v i v i + 1 A ( D ) . If J i is trivial, then we have v i = v i . Since J i is strong, J i contains a ( v i , v i ) -path P i . Thus

C : = P 1 v 1 v 2 P 2 v 2 v 3 v i 1 v i P i v i v i + 1 P i + 1 v s 1 v s P s v s v 1

is a cycle of D with C [ v i , v i ] being a path in J i , for each i 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 , , 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 [ k 1 ] . 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 V ( H 1 ) V ( H 2 ) , then H 1 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 V ( D ) , 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 D 1 × D 2 is a circulation.

(ii) If H1 and H2 are arc-disjoint subdigraphs of D1, then H 1 × D 2 and H 2 × D 2 are arc-disjoint subdigraphs of D 1 × D 2 .

(iii) If each of D1 and D2 has a cycle factor, then D 1 × D 2 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 ( u i , v j ) V 1 × V 2 , d D 1 × D 2 + ( ( u i , v j ) ) = d D 1 × D 2 ( ( u i , v j ) ) . Let ( u i , v j ) V 1 × V 2 . Since D1 and D2 are cycles, we have | N D 1 + ( u i ) | = | N D 1 ( u i ) | and | N D 2 + ( v j ) | = | N D 2 ( v j ) | . By Definition 1.2, we have the following, which implies (i).

d D 1 × D 2 + ( ( u i , v j ) ) = | N D 1 × D 2 + ( ( u i , v j ) ) | = | { ( u s , v t ) V 1 × V 2 : ( u i , v j ) ( u s , v t ) A ( D 1 × D 2 ) } | = | { ( u s , v t ) V 1 × V 2 : u i u s A ( D 1 ) and v j v t A ( D 2 ) } | = u s N D 1 + ( u i ) v t N D 2 + ( v j ) | { ( u s , v t ) V 1 × V 2 } | = | N D 1 + ( u i ) | | N D 2 + ( v j ) | = | N D 1 ( u i ) | | N D 2 ( v j ) |

= u s N D 1 ( u i ) v t N D 2 ( v j ) | { ( u s , v t ) V 1 × V 2 } | = | { ( u s , v t ) V 1 × V 2 : u s u i A ( D 1 ) and v t v j A ( D 2 ) } | = | N D 1 × D 2 ( ( u i , v j ) ) | = | { ( u s , v t ) V 1 × V 2 : ( u s , v t ) ( u i , v j ) A ( D 1 × D 2 ) } | = d D 1 × D 2 ( ( u i , v j ) )

To prove (ii), let H1 and H2 be an arc-disjoint subdigraph of D1. If there exists an arc

( u i , v j ) ( u s , v t ) A ( H 1 × D 2 ) A ( H 2 × D 2 ) ,

then by Definition 1.2, we must have u i u s H 1 H 2 . Hence if H1 and H2 are arc-disjoint subdigraphs of D1, then H 1 × D 2 and H 2 × D 2 are arc disjoint subdigraphs of D 1 × D 2 .

To prove (iii), let F1 and F2 be the spanning circulations of D1 and D2, respectively. By Definition 1.2, F 1 × F 2 is spanning subdigraph of D 1 × D 2 . By (i), F 1 × F 2 is a circulation, and so F 1 × F 2 is the spanning circulation of D 1 × D 2 . Thus F 1 × F 2 is a cycle factor of D 1 × D 2 . ∎

Lemma 2.5. Let D1, D2 be digraphs and F be a subdigraph of D1. Then A ( F D 2 ) A ( F × D 2 ) = .

Proof. Suppose that there exists an arc ( u i , v j ) ( u s , v t ) A ( F D 2 ) A ( F × D 2 ) . By Definition 1.2 (i), as ( u i , v j ) ( u s , v t ) A ( F D 2 ) , we have either u i = u s and v j v t A ( D 2 ) or

u i u s A ( F ) and v j = v t . By Definition 1.2 (ii), if u i = u s or if v j = v t , then ( u i , v j ) ( u s , v t ) A ( F × D 2 ) . It follows that A ( F D 2 ) A ( F × D 2 ) = . ∎

Theorem 2.6. (Hammack, Theorem 10.3.2 of [24] ) Let m and n be integers with m n 2 and let C m and C n denote the cycles of order m and n, respectively. Let g c d ( m , n ) and l c m ( m , n ) be the greatest common divisor and the least common multiplier of m and n, respectively. Then the direct product C m × C n is a vertex disjoint union of g c m ( m , n ) cycles, each of which has length l c m ( m , n ) .

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 v V ( D 2 ) is an arbitrarily given vertex. Then for any cycle C in D 1 × D 2 , there exists a vertex u V ( D 1 ) such that the vertex ( u , v ) V ( C ) .

(ii) Suppose that D1 and D2 are circulations and v V ( D 2 ) is an arbitrarily given vertex. Then D 1 × D 2 is also a circulation. Moreover, for any eulerian subdigraph F in D 1 × D 2 , there exists a vertex u V ( D 1 ) such that the vertex ( u , v ) V ( F ) .

Proof. Suppose D 1 = u 1 u 2 u n 1 u 1 and D 2 = v 1 v 2 v n 2 v 1 are cycles, and by symmetry, assume that v = v 1 . Let C be a cycle in D 1 × D 2 . Thus C contains a vertex ( u i , v j ) . It follows by Definition 1.2 that

C = ( u i , v j ) ( u i + 1 , v j + 1 ) ( u i + n 2 j , v n 2 ) ( u i + n 2 j + 1 , v 1 )

where the subscripts of vertices in D1 are taken in n 1 and those of vertices in D2 are taken in n 2 . It follows that u = u i + n 2 j + 1 . 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, D 1 × D 2 is also a circulation. Let F be an eulerian subdigraph in D 1 × D 2 . By (2), F is also an arc-disjoint union of cycles C 1 , C 2 , . 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 D1 and D2 are two strong digraphs, and for some cycle factor F of D1, D1/F is hamiltonian with f ( D 2 ) | V ( D 1 ) | . We start with some notation for the copies of factors in the Cartesian product.

Definition 3.1. Let D 1 = ( V 1 , A 1 ) and D 2 = ( V 2 , A 2 ) be two strong digraphs with V 1 = { u 1 , u 2 , , u n 1 } and V 2 = { v 1 , v 2 , , v n 2 } . For i { 1 , 2 } , let H i be a subdigraph of D i .

(i) For each u V 1 , let D 2 u be the subdigraph of D 1 D 2 induced by V ( D 2 u ) = { ( u , v i ) : 1 i n 2 } . The subdigraph D 2 u is called the u-copy of D2 in D 1 D 2 .

(ii) For each v V 2 , let D 1 v be the subdigraph of D 1 D 2 induced by V ( D 1 v ) = { ( u i , v ) : 1 i n 1 } . The subdigraph D 1 v is called the v-copy of D1 in D 1 D 2 .

(iii) More generally, for each u V 1 (or v 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 ( H 2 u ) = { ( u , v i ) ( u , v i ) : v i v i A ( H 2 ) } (or A ( H 1 v ) = { ( u i , v ) ( u i , v ) : u i u i A ( H 1 ) } , respectively). The subdigraph H 1 v is called the v-copy of H1 in D 1 D 2 and the subdigraph H 2 u is called the u-copy of H2 in D 1 D 2 .

If two digraphs D and H are isomorphic, then we write D H . The following is an immediate observation from Definition 3.1 for the Cartesian product D 1 D 2 of two digraphs D1 and D2.

For any v V ( D 2 ) , D 1 D 1 v , and for any u V ( D 1 ) , D 2 D 2 u . (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

F 1 , F 2 , , F k be the components of F, and J = D 1 / F . (4)

Then V ( J ) = { w 1 , w 2 , , w k } , where for each i [ k ] , w i is the contraction image in J of the eulerian subdigraph F i in D1. SinceJ is hamiltonian, we may by symmetry assume that C = w 1 w 2 w k w 1 is a hamilton cycle ofJ. It follows by Lemma 2.1 that

D1 has a cycle C with A ( C ) A ( C ) . (5)

Now we consider D2. Let f ( D 2 ) = m | V ( D 1 ) | and F be a circulation of D2 such that D 2 / F has a cycle vertex cover C = { C 1 , C 2 , , C m } . Let F 1 , F 2 , , F k be the components of F , w k + 1 , , w t be the vertices in V ( D 2 ) V ( F ) . We define, for each i with k + 1 i t , F i to be the digraph with V ( F i ) = { w i } and A ( F i ) = . With these definitions, we have

V ( D 2 / F ) = { w 1 , w 2 , , w k , w k + 1 , , w t } (6)

By Lemma 2.1, for each j [ m ] , C j in C 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 [ k ] , and j [ t ] , F i × F j is a circulation.

(ii) For any i [ k ] , and j [ t ] , F i F j is an eulerian digraph.

(iii) For any i [ k ] , and for each j [ t ] , if v V ( F j ) , then F i v ( F i × F j ) is a spanning eulerian subdigraph F i F j .

Proof. For each i [ k ] , F i is an eulerian subdigraph of D 1 , so F i is a disjoint union of cycles. Similarly, for each j [ k ] , F j is an eulerian sudigraph of D 2 , so F j is a disjoint union of cycles. By Lemma 2.7, F i × F j is a circulation.

By assumption, for each i [ k ] , F i is an eulerian subdigraph of D 1 . If j [ k ] , then as F j is an eulerian sudigraph of D 2 , it follows by Theorem 1.5 (i) that F i F j is an eulerian digraph.

Now assume that k + 1 j t . Then V ( F j ) = { w j } , and so by (3), F i F j = F i w j F i is eulerian. This proves (ii).

For each i [ k ] , each j [ t ] and a fixed vertex v V ( F j ) , let J = F i v ( F i × F j ) . By (i), F i × F j is a circulation. By (3), F i v F i is an eulerian digraph. By Lemma 2.5, A ( F i v ) A ( F i × F j ) = . It follows that for any vertex z V ( J ) ,

d J + ( z ) = d F i v + ( z ) + d F i × F j + ( z ) = d F i v ( z ) + d F i × F j ( z ) = d J ( z )

and so J is a circulation. Without loss of generality, we denote V ( F i ) = { u i 1 , u i 2 , , u i t i } and V ( F j ) = { v j 1 , v j 2 , , v j s j } with v = v j 1 . To prove that J is connected, let z 0 = ( u i 1 , v j 1 ) V ( J ) and let J 1 be the connected component of J that contains z 0 . If J is not connected, then by symmetry, we may assume that there exists a vertex ( u i 2 , v j 2 ) V ( J ) V ( J 1 ) . As F i × F j is a circulation, there must be an eulerian subdigraph F of F i × F j with

( u i 2 , v j 2 ) V ( F ) . By Lemma 2.7 (ii), there exists a vertex u V ( D 1 ) such that ( u , v j 1 ) V ( F ) . Thus by Definition 3.1 (ii), V ( F ) V ( F i v ) . By (3) and (4), F i v F i is connected, and so both ( u i 1 , v j 1 ) and ( u , v j 1 ) must be in the same component of J . This implies that ( u , v j 1 ) V ( J 1 ) . Since ( u i 2 , v j 2 ) and ( u , v j 1 ) are in the same component of J , It follows that ( u i 2 , v j 2 ) V ( J 1 ) also, contrary to the assumption that ( u i 2 , v j 2 ) V ( J ) V ( J 1 ) . Hence J must be connected, and so F i v ( F i × F j ) is a spanning eulerian subdigraph F i F j . ∎

Claim 2. Let C be a Hamilton cycle of J and C be a lift of C in D 1 as warranted by (5). For each v V ( D 2 ) , let C v denote the v-copy of C in D 1 D 2 . For each j [ t ] , if v , v V ( F j ) are two distinct vertices, then

H v , v ; j : = i = 1 k ( F i v ( F i × F j ) ) C v

is a spanning eulerian subdigraph D 1 F j .

Proof. By Lemma 2.1. for any v V ( D 2 ) , C v has the property that for any i [ k ] , V ( C v ) V ( F i v ) . By Claim 1 (iii), for any i [ k ] and for any j [ t ] , F i v ( F i × F j ) is a spanning eulerian subdigraph F i F j and so F i v ( F i × F j ) is a strong subdigraph of D 1 F j . Since for any i [ k ] , V ( C v ) V ( F i v ) , we may assume that for some vertex u V ( F i ) , ( u , v ) V ( C v ) V ( F i v ) . As v V ( F j ) , we have ( u , v ) V ( C v ) V ( F i v ( F i × F j ) ) and so F i v ( F i × F j ) C v is connected. Since v v , A ( C v ) A ( F i v ( F i × F j ) ) = , we conclude from the facts that C v and F i × F j are circulations (see Claim 1 (i)) that F i v ( F i × F j ) C v is eulerian. As i [ k ] is arbitrary, we conclude that

H v , v ; j : = i = 1 k ( F i v ( F i × F j ) ) C v

is an eulerian subdigraph with vertex set V ( H v , v ; j ) = i = 1 k ( F i × F j ) = V ( D 1 F j ) . This proves Claim 2. ∎

Claim 3 Let u V ( D 1 ) be an arbitrary vertex, F be a circulation of D 2 such that D 2 / F has a cycle vertex cover C = { C 1 , C 2 , , C m } with m = f ( D 2 ) | V ( D 1 ) | . Each of the following holds.

(i) F u is a circulation of D 2 u .

(ii) For any j [ m ] , C j u is a cycle of D 2 u / F u and { C 1 u , C 2 u , , C m u } is a cycle vertex cover of D 2 u / F u .

(iii) Let u V ( D 1 ) be a vertex, h [ m ] be arbitrarily given. For any vertex w j V ( C h ) , let v ( j ) , v ( j ) be two distinct vertices in V ( F j ) , and C h be a lift of C h in D 2 . Then

H h u = [ w j V ( C h ) H v ( j ) , v ( j ) ; j ] C h u

is an eulerian digraph with V ( H h u ) = v j V ( C h ) V ( D 1 v j ) .

Proof. Each of (i) and (ii) follows from (3) and the definition of C . It remains to prove (iii). By Lemma 2.1, C h can be lifted to a cycle C h in D 2 . For any w j V ( C h ) , pick two distinct vertices v , v V ( F j ) . By Claim 2, H v , v ; j defined in Claim 2 is a spanning eulerian subdigraph D 1 F j . By Lemma 2.5, C h u = D 1 [ { u } ] C h is arc-disjoint from each H v , v ; j , and so by the facts that C h u is a directed cycle and H v , v ; j is eulerian, it follows that H h u is a circulation. By Definition 3.1 (iii) and by Lemma 2.5, w j V ( C h ) if and only if V ( C h u ) V ( F j u ) . This is equivalent to saying that a vertex w j V ( C h ) if and only if for some vertex v V ( F j ) with ( u , v ) V ( C h u ) . Since C h u is a cycle, and since, for each w j V ( C h ) , there exists some vertex v V ( F j ) with ( u , v ) V ( C h u ) , we obtain that V ( H v , v ; j ) V ( C h u ) contains a vertex ( u , v ) , 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 ( C h u ) w j V ( C h ) V ( D 1 F j ) .

This, together with Claim 2, implies

V ( H h u ) = w j V ( C h ) ( H v ( j ) , v ( j ) ; j ) V ( C h u ) = w j V ( C h ) V ( D 1 F j ) = v j V ( C h ) V ( D 1 v j ) .

This completes the proof of Claim 3. ∎

Recall that V ( D 1 ) = { u 1 , u 2 , , u n 1 } with n 1 m = f ( D 2 ) . We will complete the proof of Theorem 1.6 by proving that

H = h = 1 m H h u h

is a spanning eulerian subdigraph of D 1 D 2 . By Claim 3 (iii), we conclude that

V ( H ) = j = 1 t V ( D 1 F j ) = V ( D 1 D 2 ) .

As u 1 , u 2 , , u m are mutually distinct, and as F 1 , F 2 , , F 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 that contains H 1 u 1 . If H = H , then done. Assume that V ( H ) V ( H ) .

Since H is a component, if some H h u h contains a vertex in H , then H contains H h u h as subdigraph. Thus every H h u h is either contained in H or totally disjoint from H . Let W = { w j V ( D 2 / F ) : H j u j iscontainedin H } . Then as H H , V ( D 2 / F ) W . Since C is a cycle vertex cover of D 2 / F , it follows by Definition 1.3 (i-2) that there must be a cycle C j C such that C j contains a vertex w W and a vertex w ( D 2 / F ) W . Since w W , H j u j is contained in H . Since w , w V ( C j ) , it follows that w W , contrary to the fact that w ( D 2 / F ) W . This contradiction indicates that we must have H = H , 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).

Cite this paper: Lai, H. , Lasfar, O. and Liu, J. (2021) Supereulerian Digraph Strong Products. Applied Mathematics, 12, 370-382. doi: 10.4236/am.2021.124026.
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

 
 
Top