<i>Supereulerian Digraph</i> Strong Products

Abstract

A vertex cycle cover of a digraph H is a collection C = { C 1 , C 2 , …, 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 1 and D 2 are nontrivial strong digraphs such that D 1 is supereulerian and D 2 has a cycle vertex cover C’ with |C’| ≤ | V ( D 1 )|, then the Cartesian product D 1 and D 2 is also supereulerian. In this paper, we prove that for strong digraphs D 1 and D 2 , if for some cycle factor F 1 of D 1 , the digraph formed from D 1 by contracting arcs in F1 is hamiltonian with f ( D 2 ) not bigger than | V ( D 1 )|, then the strong product D 1 and D 2 is supereulerian.