文献详情
On perfect matchings in matching covered graphs
文献类型：期刊
通讯作者：Ye, D (reprint author), Middle Tennessee State Univ, Dept Math Sci, Murfreesboro, TN 37132 USA.; Ye, D (reprint author), Middle Tennessee State Univ, Ctr Computat Sci, Murfreesboro, TN 37130 USA.
期刊名称：JOURNAL OF GRAPH THEORY影响因子和分区
年：2019
卷：90
期：4
页码：535-546
ISSN：0364-9024
关键词：matching-covered graph; perfect matching
摘要：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 vertical bar M-1 boolean AND X vertical bar not equivalent to vertical bar M-2 boolean AND X vertical bar (mod 2), and an edge subset K with at least two edges is an equivalent se ...More
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 vertical bar M-1 boolean AND X vertical bar not equivalent to vertical bar M-2 boolean AND X vertical bar (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 empty set or E (G), which provides a negative answer to a problem of Lukot'ka and Rollova. 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 vertical bar E [A(1), B-2]vertical bar >= 2 and vertical bar E [B-1, A(2)]vertical bar >= 2. ...Hide

DOI：10.1002/jgt.22411
百度学术：On perfect matchings in matching covered graphs
语言：外文
基金：Natural Science Foundation of ChinaNational Natural Science Foundation of China [11401576]; Simons Foundation [359516]
作者其他论文



A Note on Decycling Number, Vertex Partition and AVD-Total Coloring in Graphs.Yang, Chao, Ren, Han, Wei, Erling,.GRAPHS AND COMBINATORICS. 2018, 34(6), 1325-1332.
Homeomorphically irreducible spanning trees in hexangulations of surfaces.Zhai, Shaohui, Wei, Erling, He, Jinghua, et al. .DISCRETE MATHEMATICS. 2019, 342(10,SI), 2893-2899.
Homeomorphically irreducible spanning trees in hexangulations of surfaces.Zhai, Shaohui, Wei, Erling, He, Jinghua, et al. .DISCRETE MATHEMATICS. 2019, 342(10,SI), 2893-2899.
The edge spectrum of the saturation number for small paths.Gould, Ronald J.;Tang, Wenliang;Wei, Erling,等.8th French Combinatorial Conference (FCC).2012,312(17,SI),2682-2689.
Decycling Number of Circular Graphs.Wei, Erling;Liu, Yanpei;Li, Zhaoxiang.8th International Sympsoium on Operations Research and Its Applications.2009,10,387-393.