Minimal 2-matching-covered graphs

作者：Zhou Shan^*; Zhang Heping

来源：Discrete Mathematics, 2009, 309(13): 4270-4279.

DOI：10.1016/j.disc.2009.01.005

• Perfect 2-matching
• 2-matching-covered graph
• Minimal 2-matching-covered graph

A perfect 2-matching M of a graph G is a spanning subgraph of G such that each component of M is either an edge or a cycle. A graph G is said to be 2-matching-covered if every edge of G lies in some perfect 2-matching of G. A2-matching-covered graph is equivalent to a "regularizable" graph, which was introduced and studied by Berge. A Tutte-type characterization for 2-matching-covered graph was given by Berge. A 2-matching-covered graph is minimal if G - e is not 2-matching-covered for all edges e of G. We use Berge's theorem to prove that the minimum degree of a minimal 2-matching-covered graph other than K(2) and K(4) is 2 and to prove that a minimal 2-matching-covered graph other than K(4) cannot contain a complete subgraph with at least 4 vertices.

• 出版日期2009-7-6
• 单位兰州大学