A vertex cycle cover of a digraph <i>H</i> is a collection C = {<em>C</em><sub>1</sub>, <em>C</em><sub>2</sub>, …, <em>C</em><sub><em&g...A vertex cycle cover of a digraph <i>H</i> is a collection C = {<em>C</em><sub>1</sub>, <em>C</em><sub>2</sub>, …, <em>C</em><sub><em>k</em></sub>} of directed cycles in <i>H</i> such that these directed cycles together cover all vertices in <i>H</i> and such that the arc sets of these directed cycles induce a connected subdigraph of <i>H</i>. A subdigraph <i>F</i> of a digraph <i>D</i> is a circulation if for every vertex in <i>F</i>, the indegree of <em>v</em> equals its out degree, and a spanning circulation if <i>F</i> is a cycle factor. Define <i>f</i> (<i>D</i>) to be the smallest cardinality of a vertex cycle cover of the digraph obtained from <i>D</i> by contracting all arcs in <i>F</i>, among all circulations <i>F</i> of <i>D</i>. Adigraph <i>D</i> is supereulerian if <i>D</i> has a spanning connected circulation. In [International Journal of Engineering Science Invention, 8 (2019) 12-19], it is proved that if <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> are nontrivial strong digraphs such that <em>D</em><sub>1</sub> is supereulerian and <em>D</em><sub>2</sub> has a cycle vertex cover C’ with |C’| ≤ |<em>V</em> (<em>D</em><sub>1</sub>)|, then the Cartesian product <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> is also supereulerian. In this paper, we prove that for strong digraphs<em> D</em><sub>1</sub> and <em>D</em><sub>2</sub>, if for some cycle factor <em>F</em><sub>1</sub> of <em>D</em><sub>1</sub>, the digraph formed from <em>D</em><sub>1</sub> by contracting arcs in F1 is hamiltonian with <i>f</i> (<i>D</i><sub>2</sub>) not bigger than |<em>V</em> (<em>D</em><sub>1</sub>)|, then the strong product <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> is supereulerian.展开更多
The 2-sum of two digraphs and , denoted , is the digraph obtained from the disjoint union of and by identifying an arc in with an arc in . A digraph D is supereulerian if D contains a spanning eulerian subdigraph. It ...The 2-sum of two digraphs and , denoted , is the digraph obtained from the disjoint union of and by identifying an arc in with an arc in . A digraph D is supereulerian if D contains a spanning eulerian subdigraph. It has been noted that the 2-sum of two supereulerian (or even hamiltonian) digraphs may not be supereulerian. We obtain several sufficient conditions on and for to be supereulerian. In particular, we show that if and are symmetrically connected or partially symmetric, then is supereulerian.展开更多
文摘A vertex cycle cover of a digraph <i>H</i> is a collection C = {<em>C</em><sub>1</sub>, <em>C</em><sub>2</sub>, …, <em>C</em><sub><em>k</em></sub>} of directed cycles in <i>H</i> such that these directed cycles together cover all vertices in <i>H</i> and such that the arc sets of these directed cycles induce a connected subdigraph of <i>H</i>. A subdigraph <i>F</i> of a digraph <i>D</i> is a circulation if for every vertex in <i>F</i>, the indegree of <em>v</em> equals its out degree, and a spanning circulation if <i>F</i> is a cycle factor. Define <i>f</i> (<i>D</i>) to be the smallest cardinality of a vertex cycle cover of the digraph obtained from <i>D</i> by contracting all arcs in <i>F</i>, among all circulations <i>F</i> of <i>D</i>. Adigraph <i>D</i> is supereulerian if <i>D</i> has a spanning connected circulation. In [International Journal of Engineering Science Invention, 8 (2019) 12-19], it is proved that if <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> are nontrivial strong digraphs such that <em>D</em><sub>1</sub> is supereulerian and <em>D</em><sub>2</sub> has a cycle vertex cover C’ with |C’| ≤ |<em>V</em> (<em>D</em><sub>1</sub>)|, then the Cartesian product <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> is also supereulerian. In this paper, we prove that for strong digraphs<em> D</em><sub>1</sub> and <em>D</em><sub>2</sub>, if for some cycle factor <em>F</em><sub>1</sub> of <em>D</em><sub>1</sub>, the digraph formed from <em>D</em><sub>1</sub> by contracting arcs in F1 is hamiltonian with <i>f</i> (<i>D</i><sub>2</sub>) not bigger than |<em>V</em> (<em>D</em><sub>1</sub>)|, then the strong product <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> is supereulerian.
文摘The 2-sum of two digraphs and , denoted , is the digraph obtained from the disjoint union of and by identifying an arc in with an arc in . A digraph D is supereulerian if D contains a spanning eulerian subdigraph. It has been noted that the 2-sum of two supereulerian (or even hamiltonian) digraphs may not be supereulerian. We obtain several sufficient conditions on and for to be supereulerian. In particular, we show that if and are symmetrically connected or partially symmetric, then is supereulerian.
