Premium
On perfect matchings in matching covered graphs
Author(s) -
He Jinghua,
Wei Erling,
Ye Dong,
Zhai Shaohui
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22411
Subject(s) - combinatorics , mathematics , bipartite graph , matching (statistics) , factor critical graph , edge cover , graph factorization , graph , discrete mathematics , line graph , 3 dimensional matching , voltage graph , statistics
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 G \ e 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 ∣ M 1 ∩ X ∣ ≢ ∣ M 2 ∩ X ∣( 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 ∅ or E ( G ) , which provides a negative answer to a problem of Lukot’ka and Rollová. 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 ∣ E [ A 1 , B 2 ] ∣ ≥ 2 and ∣ E [ B 1 , A 2 ] ∣ ≥ 2 .