Graphs with each edge in at most one maximum matching

被引：0
作者：
Niu, Mengyuan [1 ]
Zhang, Yipei [2 ]
Liu, Jinfeng [1 ]
Wang, Xiumei [1 ]
机构：
[1] Zhengzhou Univ, Sch Math & Stat, Zhengzhou 450001, Peoples R China
[2] North China Univ Water Resources & Elect Power, Sch Math & Stat, Zhengzhou 450046, Peoples R China
来源：
DISCRETE APPLIED MATHEMATICS | 2024年 / 349卷
基金：
中国国家自然科学基金;
关键词：
Perfect matching; Maximum matching; Bipartite graph; Factor -critical graph;
D O I：
10.1016/j.dam.2024.01.038
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
A matching in a graph is a set of pairwise nonadjacent edges. A maximum matching is a matching which covers as many vertices as possible. In this paper, using the Gallai- Edmonds Structure Theorem, we obtain a characterization of graphs each of whose edges belongs to at most one maximum matching. (c) 2024 Published by Elsevier B.V.
引用
收藏
页码：70 / 74
页数：5
相关论文
共 50 条
  • [41] A STRUCTURE THEOREM FOR MAXIMUM INTERNAL MATCHINGS IN GRAPHS
    BARTHA, M
    GOMBAS, E
    [J]. INFORMATION PROCESSING LETTERS, 1991, 40 (06) : 289 - 294
  • [42] Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
    Levit, VE
    Mandrescu, E
    [J]. DISCRETE APPLIED MATHEMATICS, 2003, 132 (1-3) : 163 - 174
  • [43] On edge contractible graphs
    Lin, Hong
    Yu, Lin
    [J]. ARS COMBINATORIA, 2017, 134 : 75 - 79
  • [44] On Graphs with a Unique Perfect Matching
    Xiumei Wang
    Weiping Shang
    Jinjiang Yuan
    [J]. Graphs and Combinatorics, 2015, 31 : 1765 - 1777
  • [45] On the matching and permanental polynomials of graphs
    Li, Wei
    [J]. DISCRETE APPLIED MATHEMATICS, 2021, 302 : 16 - 23
  • [46] Matching preclusion number of graphs
    Wang, Zhao
    Mao, Yaping
    Cheng, Eddie
    Zou, Jinyu
    [J]. THEORETICAL COMPUTER SCIENCE, 2019, 759 : 61 - 71
  • [47] Minimal graphs for matching extensions
    Costa, M. -C.
    de Werra, D.
    Picouleau, C.
    [J]. DISCRETE APPLIED MATHEMATICS, 2018, 234 : 47 - 55
  • [48] Game matching number of graphs
    Cranston, Daniel W.
    Kinnersley, William B.
    Suil, O.
    West, Douglas B.
    [J]. DISCRETE APPLIED MATHEMATICS, 2013, 161 (13-14) : 1828 - 1836
  • [49] On Graphs with a Unique Perfect Matching
    Wang, Xiumei
    Shang, Weiping
    Yuan, Jinjiang
    [J]. GRAPHS AND COMBINATORICS, 2015, 31 (05) : 1765 - 1777
  • [50] Unique maximum matching algorithms
    Gabow, HN
    Kaplan, H
    Tarjan, RE
    [J]. JOURNAL OF ALGORITHMS, 2001, 40 (02) : 159 - 183
12345