On perfect matchings in matching covered graphs

摘要

A graph G is matching-covered if every edge of G is contained in a perfect matching. A matching-covered graph G is strongly coverable if, for any edge e of G, the subgraph Ge is still matching-covered. An edge subset X of a matching-covered graph G is feasible if there exist two perfect matchings M-1 and M-2 such that vertical bar M-1 boolean AND X vertical bar not equivalent to vertical bar M-2 boolean AND X vertical bar (mod 2), and an edge subset K with at least two edges is an equivalent set if a perfect matching of G contains either all edges in K or none of them. A strongly matchable graph G does not have an equivalent set, and any two independent edges of G form a feasible set. In this paper, we show that for every integer k >= 3, there exist infinitely many k-regular graphs of class 1 with an arbitrarily large equivalent set that is not switching-equivalent to either empty set or E (G), which provides a negative answer to a problem of Lukot'ka and Rollova. For a matching-covered bipartite graph G(A, B), we show that G(A, B) has an equivalent set if and only if it has a 2-edge-cut that separates G(A, B) into two balanced subgraphs, and G(A, B) is strongly coverable if and only if every edge-cut separating G(A, B) into two balanced subgraphs G(1)(A(1), B-1) and G(2)(A(2), B-2) satisfies vertical bar E [A(1), B-2]vertical bar >= 2 and vertical bar E [B-1, A(2)]vertical bar >= 2.