2017/03/15 by Jinghua He, Erling Wei, He, Jinghua +5
Computer Science · Mathematics · #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #Cooperative Communication and Network Coding #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1703.05412
openalex publication_date 2017/03/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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| \pmod 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 paper, 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 provides a negative answer to 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.