GRAPHS WITH THE CIRCUIT COVER PROPERTY

被引：43

作者：

ALSPACH, B ^{[1
]}

GODDYN, L ^{[1
]}

ZHANG, CQ ^{[1
]}

机构：

[1] W VIRGINIA UNIV,DEPT MATH,MORGANTOWN,WV 26506

来源：

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY | 1994年 / 344卷 / 01期

关键词：

D O I：

10.2307/2154711

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A circuit cover of an edge-weighted graph (G, p) is a multiset of circuits in G such that every edge e is contained in exactly p(e) circuits in the multiset. A nonnegative integer valued weight vector p is admissible if the total weight of any edge-cut is even, and no edge has more than half the total weight of any edge-cut containing it. A graph G has the circuit cover property if (G, p) has a circuit cover for every admissible weight vector p . We prove that a graph has the circuit cover property if and only if it contains no subgraph homeomorphic to Petersen's graph. In particular, every 2-edge-connected graph with no subgraph homeomorphic to Petersen's graph has a cycle double cover.

引用

页码：131 / 154

页数：24

共 47 条

[1] COVERING MULTIGRAPHS BY SIMPLE CIRCUITS [J].