A NOTE ON FOUQUET-VANHERPE'S QUESTION AND FULKERSON CONJECTURE

作者：Chen, F.^*

来源：Bulletin of the Iranian Mathematical Society, 2016, 42(5): 1247-1258.

• Fulkerson-cover
• excessive index
• snark
• hypohamiltonian graph

The excessive index of a bridgeless cubic graph G is the least integer k, such that G can be covered by k perfect matchings. An equivalent form of Fulkerson conjecture (due to Berge) is that every bridgeless cubic graph has excessive index at most five. Clearly, Petersen graph is a cyclically 4-edge-connected snark with excessive index at least 5, so Fouquet and Vanherpe asked whether Petersen graph is the only one with that property. Hagglund gave a negative answer to their question by constructing two graphs Blowup(K-4, C) and Blowup(Prism, C-4). Based on the first graph, Esperet et al. constructed in finite families of cyclically 4-edge-connected snarks with excessive index at least five. Based on these two graphs, we construct in finite families of cyclically 4-edge-connected snarks E-0,E-1,E-2,E-...,E- (k-1) in which E-0,E-1,E-2 is Esperet et al.'s construction. In this note, we prove that E-0,E-1,E-2,E-3 has excessive index at least five, which gives a strongly negative answer to Fouquet and Vanherpe's question. As a subcase of Fulkerson conjecture, Haggkvist conjectured that every cubic hypohamiltonian graph has a Fulkerson-cover. Motivated by a related result due to Hou et al.'s, in this note we prove that Fulkerson conjecture holds on some families of bridgeless cubic graphs.

• 出版日期2016-10
• 单位安徽财经大学