|
内
容
简
介
|
Let G be a matching-covered graph, i.e., every edge is contained in a perfect matching. An edge subset X of G is feasible if there exists two perfect matchings M1 and M2 such that |M1∩X|\not ≡ |M2∩X| mod 2. Lukot'ka and Rollová proved that an edge subset X of a regular bipartite graph is not feasible if and only if X is switching-equivalent to ∅, and they further ask whether a non-feasible set of a regular graph of class 1 is always switching-equivalent to either ∅ or E(G)? Two edges of G are equivalent to each other if a perfect matching M of G either contains both of them or contains none of them. An equivalent class of G is an edge subset K with at least two edges such that the edges of K are mutually equivalent. An equivalent class is not a feasible set. Lovász proved that an equivalent class of a brick has size 2. In this talk, we show that, for every integer k ≥ 3, there exist infinitely many k-regular graphs of class 1 with an arbitrarily large equivalent class K such that K is not switching-equivalent to either ∅ or E(G), which settles the problem proposed by Lukot'ka and Rollová. Further, we characterize bipartite graphs with equivalent class, and characterize matching-covered bipartite graphs of which every edge is removable. This is joint work with He, Wei and Zhai.
|
