On perfect matchings in matching covered graphs
Jinghua He, Erling Wei, Dong Ye, Shaohui Zhai · Journal of Graph Theory · 2018
Abstract A graph is matching‐covered if every edge of is contained in a perfect matching. A matching‐covered graph is strongly coverable if, for any edge of , the subgraph is still matching‐covered. An edge subset of a matching‐covered graph is feasible if there exist two perfect matchings and such that , and an edge subset with at least two edges is an equivalent set if a perfect matching of contains either all edges in or none of them. A strongly matchable graph does not have an equivalent set, and any two independent edges of form a feasible set. In this paper, we show that for every integer , there exist infinitely many ‐regular graphs of class 1 with an arbitrarily large equivalent set that is not switching‐equivalent to either or , which provides a negative answer to a problem of Lukot’ka and Rollová. For a matching‐covered bipartite graph , we show that has an equivalent set if and only if it has a 2‐edge‐cut that separates into two balanced subgraphs, and is strongly coverable if and only if every edge‐cut separating into two balanced subgraphs and satisfies and .