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 E-2 of edges such that E-1 boolean OR E-2 is a cycle and G\E-i 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 Chvatal. (C) 2015 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
DISCRETE APPLIED MATHEMATICS
ISSN: 0166-218X
Year: 2015
Volume: 186
Page: 66-73
0 . 7 2 2
JCR@2015
1 . 0 0 0
JCR@2023
ESI Discipline: ENGINEERING;
ESI HC Threshold:183
JCR Journal Grade:3
CAS Journal Grade:4
Cited Count:
WoS CC Cited Count: 6
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: