A characterization of nonfeasible sets in matching covered graphs. Issue 4 (16th April 2020)

• Record Type: Journal Article
• Authors: Liu, Qinghai; Cui, Qing; Feng, Xing; Lu, Fuliang
• Is Part Of: Journal of graph theory. Volume 95:Issue 4(2020)
• Page Start: 509
• Page End: 526
• Publication Date: 2020-04-16
• Subjects: feasible set -- matching covered graph -- perfect matching; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22570
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: Let G be a matching covered graph and let X ⊆ E ( G ) . Then X is called feasible if there exist two perfect matchings M 1 and M 2 in G such that ∣ M 1 ∩ X ∣ ≢ ∣ M 2 ∩ X ∣ ( mod 2 ) ; otherwise, it is nonfeasible. For any vertex v ∈ V ( G ), the switching operation of X in v is defined as the symmetric difference of X and ∂ ( v ), where ∂ ( v ) denotes the set of all edges in G incident with v . Two sets X 1, X 2 ⊆ E ( G ) are switching‐equivalent if X 1 can be obtained from X 2 by a series of switching operations and vice visa. Lukot'ka and Rollová showed that if G is a regular bipartite graph, then X is nonfeasible if and only if X is switching‐equivalent to ∅ (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 ∅ and E ( G ) if and only if G is bipartite, and X is switching‐equivalent to either ∅ 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 ∅ or E ( G ) . This gives negative answers to two problems proposed by Lukot'ka and Rollová and by He et al, respectively.