Abstract :
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. H\ {a}gglund gave a negative answer to their question by constructing two graphs Blowup(K4,C) and Blowup(Prism,C4). Based on the first graph, Esperet et al. constructed infinite families of cyclically 4-edge-connected snarks with excessive index at least five. Based on these two graphs, we construct infinite families of cyclically 4-edge-connected snarks E0,1,2,…,(k−1) in which E0,1,2 is Esperet et al. s construction. In this note, we prove that E0,1,2,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, H\ {a}ggkvist 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.
Keywords :
Fulkerson , cover , excessive index , snark , hypohamiltonian graph