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
基金
中国国家自然科学基金;
关键词
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 条
[31]   On the Independent Domination Number of Regular Graphs [J].
Goddard, Wayne ;
Henning, Michael A. ;
Lyle, Jeremy ;
Southey, Justin .
ANNALS OF COMBINATORICS, 2012, 16 (04) :719-732
[32]   ON THE TOTAL DOMATIC NUMBER OF REGULAR GRAPHS [J].
Aram, H. ;
Sheikholeslami, S. M. ;
Volkmann, L. .
TRANSACTIONS ON COMBINATORICS, 2012, 1 (01) :45-51
[33]   On independent domination number of regular graphs [J].
Lam, PCB ;
Shiu, WC ;
Sun, L .
DISCRETE MATHEMATICS, 1999, 202 (1-3) :135-144
[34]   Turan number of complete bipartite graphs with bounded matching number [J].
Luo, Huan ;
Zhao, Xiamiao ;
Lu, Mei .
DISCRETE MATHEMATICS, 2025, 348 (09)
[35]   Connected Domination Number and a New Invariant in Graphs with Independence Number Three [J].
Bercov, Vladimir .
COMPUTER SCIENCE JOURNAL OF MOLDOVA, 2021, 29 (01) :96-104
[36]   On the permanental nullity and matching number of graphs [J].
Wu, Tingzeng ;
Lai, Hong-Jian .
LINEAR & MULTILINEAR ALGEBRA, 2018, 66 (03) :516-524
[37]   On the nullity and the matching number of unicyclic graphs [J].
Guo, Ji-Ming ;
Yan, Weigen ;
Yeh, Yeong-Nan .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2009, 431 (08) :1293-1301
[38]   On the independence number of graphs with maximum degree 3 [J].
Kanj, Iyad ;
Zhang, Fenghui .
THEORETICAL COMPUTER SCIENCE, 2013, 478 :51-75
[39]   The spectral radius of graphs with given independence number [J].
Lou, Zhenzhen ;
Guo, Ji-Ming .
DISCRETE MATHEMATICS, 2022, 345 (04)
[40]   On the Connectivity and Independence Number of Power Graphs of Groups [J].
Peter J. Cameron ;
Sayyed Heidar Jafari .
Graphs and Combinatorics, 2020, 36 :895-904