Cycle Cover, Integer Flow, and Fulkerson Conjecture
主 题: Cycle Cover, Integer Flow, and Fulkerson Conjecture
报告人: 范更华 (福州大学)
时 间: 2014-05-23 15:00-16:00
地 点: 理科一号楼1114（数学所活动）
A cycle is a graph in which each vertex is incident with an even number of edges. A cycle cover of a graph G is a set of cycles such that each edge of G is in at least one of the cycles. An integer k-?ow in a graph G with an orientation is a function f from the edge set of G to an abelian group of order k such that at each vertex v, the sum of f(e) over all the edges entering v is equal to the sum of f(e) over all the edges leaving v. Recently we obtained a result on integer 4-?ows, which was used to improve the existing results on cycle covers. The Fulkerson Conjecture asserts that every bridgeless graph G has a set of six cycles such that each edge of G is in exactly four of the cycles. We verify the Fulkerson Conjecture for several classes of graphs. Problems related to the Fulkerson Conjecture are also discussed.
