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

共 13 条

[1] Forbidden subgraphs and the Konig-Egervary property [J].

Bonomo, Flavia ;

Dourado, Mitre C. ;

Duran, Guillermo ;

Faria, Luerbio ;

Grippo, Luciano N. ;

Safe, Martin D. .

DISCRETE APPLIED MATHEMATICS, 2013, 161 (16-17) :2380-2388

[2] On the number of vertices belonging to all maximum stable sets of a graph [J].

Boros, E ;

Golumbic, MC ;

Levit, VE .

DISCRETE APPLIED MATHEMATICS, 2002, 124 (1-3) :17-25

[3] KONIG-EGERVARY GRAPHS, 2-BICRITICAL GRAPHS AND FRACTIONAL MATCHINGS [J].

BOURJOLLY, JM ;

PULLEYBLANK, WR .

DISCRETE APPLIED MATHEMATICS, 1989, 24 (1-3) :63-82

[4] New Results Relating Independence and Matchings [J].

Caro, Yair ;

Davila, Randy ;

Pepper, Ryan .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2022, 42 (03) :921-935

[5] INDEPENDENCE NUMBERS OF GRAPHS - EXTENSION OF THE KOENIG-EGERVARY THEOREM [J].

DEMING, RW .

DISCRETE MATHEMATICS, 1979, 27 (01) :23-33

[6]

Hall Philip, 1935, J LOND MATH SOC, P26, DOI DOI 10.1112/JLMS/S1-10.37.26

[7] The critical independence number and an independence decomposition [J].

Larson, C. E. .

EUROPEAN JOURNAL OF COMBINATORICS, 2011, 32 (02) :294-300

[8]

Levit V., ARXIV

[9] On maximum matchings in Konig-Egervary graphs [J].

Levit, Vadim E. ;

Mandrescu, Eugen .

DISCRETE APPLIED MATHEMATICS, 2013, 161 (10-11) :1635-1638

[10] Cubic graphs with equal independence number and matching number [J].

Mohr, Elena ;

Rautenbach, Dieter .

DISCRETE MATHEMATICS, 2021, 344 (01)

← 1 2 →