A vertex cycle cover of a digraph H is a collection C = {C<sub>1</sub>, C<sub>2</sub>, …, C<sub>k</sub>} of directed cycles in H such that these directed cycles together cover all ...A vertex cycle cover of a digraph H is a collection C = {C<sub>1</sub>, C<sub>2</sub>, …, C<sub>k</sub>} 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<sub>1</sub> and D<sub>2</sub> are nontrivial strong digraphs such that D<sub>1</sub> is supereulerian and D<sub>2</sub> has a cycle vertex cover C’ with |C’| ≤ |V (D<sub>1</sub>)|, then the Cartesian product D<sub>1</sub> and D<sub>2</sub> is also supereulerian. In this paper, we prove that for strong digraphs D<sub>1</sub> and D<sub>2</sub>, if for some cycle factor F<sub>1</sub> of D<sub>1</sub>, the digraph formed from D<sub>1</sub> by contracting arcs in F1 is hamiltonian with f (D<sub>2</sub>) not bigger than |V (D<sub>1</sub>)|, then the strong product D<sub>1</sub> and D<sub>2</sub> is supereulerian.展开更多
A digraph D is supereulerian if D has a spanning eulerian subdigraph. Bang- Jensen and Thomasse conjectured that if the arc-strong connectivity ）,（D） of α digraph D is not less than the independence number α（D）...A digraph D is supereulerian if D has a spanning eulerian subdigraph. Bang- Jensen and Thomasse conjectured that if the arc-strong connectivity ）,（D） of α digraph D is not less than the independence number α（D）, then D is supereulerian. In this paper, we prove that if D is an extended cycle, an extended hamiltonian digraph, an arc-locally semicomplete digraph, an extended arc-locally semicomplete digraph, an extension of two kinds of eulerian digraph, a hypo-semicomplete digraph or an extended hypo-semicomplete digraph satisfying λ（D） ≥α（D）, then D is supereulerian.展开更多
A digraph D is oriented if it does not contain 2-cycles. If an oriented digraph D has a directed eulerian path, it is an oriented eulerian digraph. In this paper, when an oriented eulerian digraph D has minimum out-de...A digraph D is oriented if it does not contain 2-cycles. If an oriented digraph D has a directed eulerian path, it is an oriented eulerian digraph. In this paper, when an oriented eulerian digraph D has minimum out-degree 2 and a diameter d, we find the minimum order of D. In addition, when D is 2-regular with diameter 4rn （m≥2）, we classify the extremal cases.展开更多
文摘A vertex cycle cover of a digraph H is a collection C = {C<sub>1</sub>, C<sub>2</sub>, …, C<sub>k</sub>} 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<sub>1</sub> and D<sub>2</sub> are nontrivial strong digraphs such that D<sub>1</sub> is supereulerian and D<sub>2</sub> has a cycle vertex cover C’ with |C’| ≤ |V (D<sub>1</sub>)|, then the Cartesian product D<sub>1</sub> and D<sub>2</sub> is also supereulerian. In this paper, we prove that for strong digraphs D<sub>1</sub> and D<sub>2</sub>, if for some cycle factor F<sub>1</sub> of D<sub>1</sub>, the digraph formed from D<sub>1</sub> by contracting arcs in F1 is hamiltonian with f (D<sub>2</sub>) not bigger than |V (D<sub>1</sub>)|, then the strong product D<sub>1</sub> and D<sub>2</sub> is supereulerian.
基金Supported by the National Natural Science Foundation of China(Grant Nos.1176107161363020)+1 种基金Science and Technology Innovation Project of Xinjiang Normal University(Grant No.XSY201602013)the"13th Five-Year"Plan for Key Discipline Mathematics of Xinjiang Normal University(Grant No.17SDKD1107)
文摘A digraph D is supereulerian if D has a spanning eulerian subdigraph. Bang- Jensen and Thomasse conjectured that if the arc-strong connectivity ）,（D） of α digraph D is not less than the independence number α（D）, then D is supereulerian. In this paper, we prove that if D is an extended cycle, an extended hamiltonian digraph, an arc-locally semicomplete digraph, an extended arc-locally semicomplete digraph, an extension of two kinds of eulerian digraph, a hypo-semicomplete digraph or an extended hypo-semicomplete digraph satisfying λ（D） ≥α（D）, then D is supereulerian.
基金Supported by the University of Incheon Research Grant in 2009-2010
文摘A digraph D is oriented if it does not contain 2-cycles. If an oriented digraph D has a directed eulerian path, it is an oriented eulerian digraph. In this paper, when an oriented eulerian digraph D has minimum out-degree 2 and a diameter d, we find the minimum order of D. In addition, when D is 2-regular with diameter 4rn （m≥2）, we classify the extremal cases.
