EULERIAN SUBGRAPHS CONTAINING GIVEN VERTICES

被引：1

作者：

Zhang, Zhao ^{[1
]}

Li, Hao ^{[2
]}

机构：

[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Xinjiang, Peoples R China

[2] Univ Paris 11, CNRS, UMR 8623, Rech Informat Lab, F-91405 Orsay, France

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2011年 / 25卷 / 02期

关键词：

Eularian subgraph; cyclable set; edge disjoint paths; HAMILTONIAN LINE GRAPHS; SUPEREULERIAN GRAPHS;

D O I：

10.1137/060663337

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A vertex set S subset of V(G) is k-weak-edge-connected if, for every C subset of S and x is an element of S - C, there are min{k, vertical bar C vertical bar} edge-disjoint (x, C)-paths in G. For a graph G and a k-weak-edge-connected vertex set S subset of V(G) with k >= 3 and 4 <= vertical bar S vertical bar <= 2k, we show that G has an Eulerian subgraph containing all vertices in S.

引用

页码：611 / 621

页数：11

共 21 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2]

[Anonymous], 2013, Modern graph theory

[3]

Bondy J. A., 1976, Graduate Texts in Mathematics, V290

[4] SUPEREULERIAN GRAPHS - A SURVEY [J].

CATLIN, PA .

JOURNAL OF GRAPH THEORY, 1992, 16 (02) :177-196

[5] Supereulerian graphs and the Petersen graph [J].

Catlin, PA ;

Lai, HJ .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1996, 66 (01) :123-139

[6] Eulerian subgraphs in 3-edge-connected graphs and Hamiltonian line graphs [J].

Chen, ZH ;

Lai, HJ ;

Li, XW ;

Li, DY ;

Mao, JZ .

JOURNAL OF GRAPH THEORY, 2003, 42 (04) :308-319

[7]

CHEN ZH, COMBINATORICS GRAPH, V1, P53

[8]

Chvatal V., 1973, NEW DIRECTIONS THEOR, P65

[9]

DIRAC GA, 1960, MATH NACHR, V22, P61

[10]

FLANDRIN E, COMMUNICATION

← 1 2 3 →