Regular graphs with equal matching number and independence number

被引：2
作者：
Yang, Zixuan [1 ]
Lu, Hongliang [1 ]
机构：
[1] Xi An Jiao Tong Univ, Sch Math & Stat, Xian 710049, Shaanxi, Peoples R China
来源：
DISCRETE APPLIED MATHEMATICS | 2022年 / 310卷
基金：
中国国家自然科学基金;
关键词：
Independence number; Matching number; Regular graph;
D O I：
10.1016/j.dam.2021.12.023
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Let r >= 3 be an integer and G be a graph. Let delta(G), Delta(G), alpha(G), and mu(G) denote the minimum degree, maximum degree, independence number, and matching number of G, respectively. Recently, Caro, Davila and Pepper proved delta(G)alpha(G) <= Delta(G)mu(G). Mohr and Rautenbach characterized the extremal graphs within the classes of all non-regular graphs and 3-regular graphs. In this note, we characterize the extremal graphs within the classes of all r-regular graphs in terms of the Gallai-Edmonds Structure Theorem, which extends Mohr and Rautenbach's result. (C) 2021 Elsevier B.V. All rights reserved.
引用
收藏
页码：86 / 90
页数：5
相关论文
共 50 条
[41]   A new lower bound on the independence number of graphs [J].
Angel, Eric ;
Campigotto, Romain ;
Laforest, Christian .
DISCRETE APPLIED MATHEMATICS, 2013, 161 (06) :847-852
[42]   Independence Number and k-Trees of Graphs [J].
Yan, Zheng .
GRAPHS AND COMBINATORICS, 2017, 33 (05) :1089-1093
[43]   Local transformations of graphs preserving independence number [J].
Alekseev, VE ;
Lozin, VV .
DISCRETE APPLIED MATHEMATICS, 2004, 135 (1-3) :17-30
[44]   ON THE INDEPENDENCE NUMBER OF EDGE CHROMATIC CRITICAL GRAPHS [J].
Pang, Shiyou ;
Miao, Lianying ;
Song, Wenyao ;
Miao, Zhengke .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2014, 34 (03) :577-584
[45]   On the Structure of Hamiltonian Graphs with Small Independence Number [J].
Jedlickova, Nikola ;
Kratochvil, Jan .
COMBINATORIAL ALGORITHMS, IWOCA 2024, 2024, 14764 :180-192
[46]   On the Independence Number of Edge Chromatic Critical Graphs [J].
Miao Lianying .
ARS COMBINATORIA, 2011, 98 :471-481
[47]   Admissible Property of Graphs in Terms of Independence Number [J].
Hua, Hongbo ;
Hua, Xinying .
BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2022, 45 (05) :2123-2135
[48]   Embedding trees in graphs with independence number two [J].
Hu, Xiaolan ;
Chen, Yaojun .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2018, 10 (04)
[49]   On the independence transversal total domination number of graphs [J].
Cabrera Martinez, Abel ;
Sigarreta Almira, Jose M. ;
Yero, Ismael G. .
DISCRETE APPLIED MATHEMATICS, 2017, 219 :65-73
[50]   On the Connectivity and Independence Number of Power Graphs of Groups [J].
Cameron, Peter J. ;
Jafari, Sayyed Heidar .
GRAPHS AND COMBINATORICS, 2020, 36 (03) :895-904
12345