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.展开更多
Two methods for determining the supereulerian index of a graph G are given. A sharp upper bound and a sharp lower bound on the supereulerian index by studying the branch bonds of G are got.
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.展开更多
A graphG is supereulerian if G has a spanning eulerian subgraph.Boesch et al.[J.Graph Theory,1,79–84（1977）]proposed the problem of characterizing supereulerian graphs.In this paper,we prove that any 3-edge-connecte...A graphG is supereulerian if G has a spanning eulerian subgraph.Boesch et al.[J.Graph Theory,1,79–84（1977）]proposed the problem of characterizing supereulerian graphs.In this paper,we prove that any 3-edge-connected graph with at most 11 edge-cuts of size 3 is supereulerian if and only if it cannot be contractible to the Petersen graph.This extends a former result of Catlin and Lai[J.Combin.Theory,Ser.B,66,123–139（1996）].展开更多
For two integers l ：〉 0 and k ≥ 0, define C（l, k） to be the family of 2-edge connected graphs such that a graph G ∈ C（l, k） if and only if for every bond S lohtain in E（G） with ｜S｜ ≤3, each component of G...For two integers l ：〉 0 and k ≥ 0, define C（l, k） to be the family of 2-edge connected graphs such that a graph G ∈ C（l, k） if and only if for every bond S lohtain in E（G） with ｜S｜ ≤3, each component of G - S has order at least （｜V（G）｜ - k）/l. In this note we prove that if a 3- edge-connected simple graph G is in C（10, 3）, then G is supereulerian if and only if G cannot be contracted to the Petersen graph. Our result extends an earlier result in [Supereulerian graphs and Petersen graph. JCMCC 1991, 9： 79-89] by Chen.展开更多
文摘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.
文摘Two methods for determining the supereulerian index of a graph G are given. A sharp upper bound and a sharp lower bound on the supereulerian index by studying the branch bonds of G are got.
文摘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.
基金Supported by National Natural Science Foundation of China(Grant No.11001287)Science Foundation Chongqing Education Committee(Grant Nos.KJ100725 and KJ120731)
文摘A graphG is supereulerian if G has a spanning eulerian subgraph.Boesch et al.[J.Graph Theory,1,79–84（1977）]proposed the problem of characterizing supereulerian graphs.In this paper,we prove that any 3-edge-connected graph with at most 11 edge-cuts of size 3 is supereulerian if and only if it cannot be contractible to the Petersen graph.This extends a former result of Catlin and Lai[J.Combin.Theory,Ser.B,66,123–139（1996）].
基金Supported by the Science Foundation of Chongqing Education Committee (Grant NoKJ100725)
文摘For two integers l ：〉 0 and k ≥ 0, define C（l, k） to be the family of 2-edge connected graphs such that a graph G ∈ C（l, k） if and only if for every bond S lohtain in E（G） with ｜S｜ ≤3, each component of G - S has order at least （｜V（G）｜ - k）/l. In this note we prove that if a 3- edge-connected simple graph G is in C（10, 3）, then G is supereulerian if and only if G cannot be contracted to the Petersen graph. Our result extends an earlier result in [Supereulerian graphs and Petersen graph. JCMCC 1991, 9： 79-89] by Chen.
