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 条
  • [21] Graphs in which some and every maximum matching is uniquely restricted
    Penso, Lucia Draque
    Rautenbach, Dieter
    Souza, Ueverton dos Santos
    JOURNAL OF GRAPH THEORY, 2018, 89 (01) : 55 - 63
  • [22] On the minimal energy of conjugated unicyclic graphs with maximum degree at most 3
    Ma, Hongping
    Bai, Yongqiang
    Ji, Shengjin
    DISCRETE APPLIED MATHEMATICS, 2015, 186 : 186 - 198
  • [23] On maximum k-edge-colorable subgraphs of bipartite graphs
    Karapetyan, Liana
    Mkrtchyan, Vahan
    DISCRETE APPLIED MATHEMATICS, 2019, 257 : 226 - 232
  • [24] A Query-Efficient Quantum Algorithm for Maximum Matching on General Graphs
    Kimmel, Shelby
    Witter, R. Teal
    ALGORITHMS AND DATA STRUCTURES, WADS 2021, 2021, 12808 : 543 - 555
  • [25] Computing maximum non-crossing matching in convex bipartite graphs
    Chen, Danny Z.
    Liu, Xiaomin
    Wang, Haitao
    DISCRETE APPLIED MATHEMATICS, 2015, 187 : 50 - 60
  • [26] An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs
    Das, Shibsankar
    SCIENTIFIC ANNALS OF COMPUTER SCIENCE, 2020, 30 (01) : 25 - 37
  • [27] Maximum number of edges in claw-free graphs whose maximum degree and matching number are bounded
    Dibek, Cemil
    Ekim, Tinaz
    Heggernes, Pinar
    DISCRETE MATHEMATICS, 2017, 340 (05) : 927 - 934
  • [28] Enumeration of Maximum Matchings of Graphs
    Wu, Tingzeng
    Zeng, Xiaolin
    Lue, Huazhong
    JOURNAL OF INTERCONNECTION NETWORKS, 2025,
  • [29] A note on upper bounds for the maximum span in interval edge-colorings of graphs
    Kamalian, R. R.
    Petrosyan, P. A.
    DISCRETE MATHEMATICS, 2012, 312 (08) : 1393 - 1399
  • [30] Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs
    Banerjee, Satyajit
    Chowdhury, Atish Datta
    Ghosh, Subhas Kumar
    INFORMATION PROCESSING LETTERS, 2009, 109 (14) : 790 - 794
12345