A characterization of nonfeasible sets in matching covered graphs

Let G be a matching covered graph and let X subset of E(G). Then X is called feasible if there exist two perfect matchings M1 and M2 in G such that divide M1 boolean AND X divide not equivalent to divide M2 boolean AND X divide (mod2); otherwise, it is nonfeasible. For any vertex v is an element of V(G), the switching operation of X in v is defined as the symmetric difference of X and partial differential (v), where partial differential (v) denotes the set of all edges in G incident with v. Two sets X1,X2 subset of E(G) are switching-equivalent if X1 can be obtained from X2 by a series of switching operations and vice visa. Lukot'ka and Rollova showed that if G is a regular bipartite graph, then X is nonfeasible if and only if X is switching-equivalent to null (as well as E(G)). In this paper, we give a complete characterization of nonfeasible sets in matching covered graphs. We prove that if G is a matching covered graph and X is an arbitrary nonfeasible set of G, then X is switching-equivalent to both null and E(G) if and only if G is bipartite, and X is switching-equivalent to either null or E(G) (but not both) if and only if G is nonbipartite and G has an ear decomposition with exactly one double ear. We also show that for any two integers s and k with s >= 2 and k >= max{3,s}, there exist infinitely many k-regular simple graphs G of class 1 with arbitrarily large brick number, connectivity s and a nonfeasible set X such that X is not switching-equivalent to either null or E(G). This gives negative answers to two problems proposed by Lukot'ka and Rollova and by He et al, respectively.