Article ID Journal Published Year Pages File Type
5776840 Discrete Mathematics 2017 8 Pages PDF
Abstract
Berge Conjecture states that every bridgeless cubic graph has 5 perfect matchings such that each edge is contained in at least one of them. In this paper, we show that Berge Conjecture holds for two classes of cubic graphs, cubic graphs with a circuit missing only one vertex and bridgeless cubic graphs having a 2-factor with exactly two circuits. The first part of this result implies that Berge Conjecture holds for hypohamiltonian cubic graphs.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,