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 条
[21]   A Characterization of Graphs with Equal Domination Number and Vertex Cover Number [J].
Wu, Yunjian ;
Yu, Qinglin .
BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2012, 35 (03) :803-806
[22]   A research on independence number in cubic graphs [J].
Liu Donglin ;
Wang Chunxiang .
PROCEEDINGS OF 2005 INTERNATIONAL CONFERENCE ON INNOVATION & MANAGEMENT, 2005, :1283-1287
[23]   Independence number of de Bruijn graphs [J].
Lichiardopol, N .
DISCRETE MATHEMATICS, 2006, 306 (12) :1145-1160
[24]   Unified bounds for the independence number of graphs [J].
Zhou, Jiang .
CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 2025, 77 (01) :97-117
[25]   Independence number of products of Kneser graphs [J].
Bresar, Bostjan ;
Valencia-Pabon, Mario .
DISCRETE MATHEMATICS, 2019, 342 (04) :1017-1027
[26]   Independence number of generalized products of graphs [J].
Mehta, H. S. ;
Acharya, U. P. .
ASIAN-EUROPEAN JOURNAL OF MATHEMATICS, 2020, 13 (01)
[27]   Independence number and [a, b]-factors of graphs [J].
Tang, Siping .
ARS COMBINATORIA, 2012, 106 :247-255
[28]   On the independence number of minimum distance graphs [J].
Csizmadia, G .
DISCRETE & COMPUTATIONAL GEOMETRY, 1998, 20 (02) :179-187
[29]   On the independence number of minimum distance graphs [J].
G. Csizmadia .
Discrete & Computational Geometry, 1998, 20 :179-187
[30]   On the Independent Domination Number of Regular Graphs [J].
Wayne Goddard ;
Michael A. Henning ;
Jeremy Lyle ;
Justin Southey .
Annals of Combinatorics, 2012, 16 :719-732