On Matching Double Covered Graphs

A graph is called 1-extendable or matching covered if each of its edges is contained in a perfect matching.This is an important class of graphs with respect,to matching theory.Especially,the studies on perfect matching polytope are in matching covered graphs.Every bridgeless cubic graph is matching covered.In 1971,Fulkerson proposed the famous Berge-Fulkerson conjecture:every bridgeless cubic graph contains a family of six perfect matchings such that each edge belongs to exactly two of them.In order to solve this conjecture,scholars have made many attempts.In 1994,Fan and Raspaud proposed a weaker conjecture that every bridgeless cubis graph contains three perfect matchings with empty intersection.Unfortunately,this weaker conjecture has not made substantive progress so far.Berge-Fulkerson conjecture is considered to be the most challenging open problems in graph theory.Scholars only proved this conjecture on some special classes of graphs.Inspired by the concept of matching covered graph and the Berge-Fulkerson conjecture,we define matching-k-covered graph.A graph is called matching-k-covered if each of its edges is contained in exactly two perfect matchings.This paper focuses on matching2-covered graphs,which is also referred as matching double covered graphs.Obviously.a matching double covered graph is matching covered.Note that a matching covered nonbipartite graph with no trivial tight cuts is a brick.This paper gives a complete characterization of matching double covered graphs.The main results are as follows:(1)If a graph G is bipartite,then G is matching double covered if and only if G is K3,3 or T1.(2)If a graph G is a brick,then G is matching double covered if and only if G is T2,T3,T4 or the Petersen graph.(3)If a graph G is nonbipartite matching covered and has no nontrivial tight cuts.then G is matching double covered if and only if G is T5,T6,T7 or T8.