Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418917 | Discrete Applied Mathematics | 2015 | 8 Pages |
Abstract
In this paper, a cycle is a graph in which each vertex has even degree. A Fulkerson-cover of a graph GG is a set of six cycles such that each edge of GG 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 GG has a Fulkerson cover if and only if there are two disjoint sets E1E1 and E2E2 of edges such that E1∪E2E1∪E2 is a cycle and G∖EiG∖Ei has a nowhere-zero 4-flow for each i=1,2i=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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Fuyuan Chen, Genghua Fan,