Indexed by:
Abstract:
In this paper, a cycle is a graph in which each vertex has even degree. A Fulkerson-cover of a graph G is a set of six cycles such that each edge of G is in exactly four of the cycles. The well-known Fulkerson-Conjecture asserts that every bridgeless graph has a Fulkerson-cover. We prove that a bridgeless graph G has a Fulkerson cover if and only if there are two disjoint sets E 1 and E2 of edges such that E1 ∪ E2 is a cycle and G\Ei has a nowhere-zero 4-flow for each i = 1, 2. Using this, together with a result of Jaeger related to crossing numbers, we verify the Fulkerson Conjecture for several known classes of hypohamiltonian graphs in the literatures, including the one based on flip-flops introduced by Chvátal. © 2015 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Source :
Discrete Applied Mathematics
ISSN: 0166-218X
Year: 2015
Issue: 1
Volume: 186
Page: 66-73
0 . 7 2 2
JCR@2015
1 . 0 0 0
JCR@2023
ESI HC Threshold:183
JCR Journal Grade:3
CAS Journal Grade:4
Cited Count:
SCOPUS Cited Count: 6
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 2
Affiliated Colleges: