Cubic graphs with equal independence number and matching number

被引：2
|
作者：
Mohr, Elena [1 ]
Rautenbach, Dieter [1 ]
机构：
[1] Ulm Univ, Inst Optimizat & Operat Res, Ulm, Germany
来源：
DISCRETE MATHEMATICS | 2021年 / 344卷 / 01期
关键词：
Independence number; Matching number;
D O I：
10.1016/j.disc.2020.112178
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Caro, Davila, and Pepper recently proved delta(G)alpha(G) <= Delta(G)mu(G) for every graph G with minimum degree delta(G), maximum degree Delta(G), independence number alpha(G), and matching number mu(G). Answering some problems they posed, we characterize the extremal graphs for delta(G) < Delta(G) as well as for delta(G) = Delta(G) = 3. (C) 2020 Elsevier B.V. All rights reserved.
引用
收藏
页数：4
相关论文
共 50 条
  • [1] Regular graphs with equal matching number and independence number
    Yang, Zixuan
    Lu, Hongliang
    DISCRETE APPLIED MATHEMATICS, 2022, 310 : 86 - 90
  • [2] Independence and matching number of some graphs
    Ming Chen
    Yusheng Li
    Yiting Yang
    Journal of Combinatorial Optimization, 2019, 37 : 1342 - 1350
  • [3] Independence and matching number of some graphs
    Chen, Ming
    Li, Yusheng
    Yang, Yiting
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 37 (04) : 1342 - 1350
  • [4] A research on independence number in cubic graphs
    Liu Donglin
    Wang Chunxiang
    PROCEEDINGS OF 2005 INTERNATIONAL CONFERENCE ON INNOVATION & MANAGEMENT, 2005, : 1283 - 1287
  • [5] On Critical Difference, Independence Number and Matching Number of Graphs
    Lu, Hongliang
    Yang, Zixuan
    GRAPHS AND COMBINATORICS, 2023, 39 (05)
  • [6] On Critical Difference, Independence Number and Matching Number of Graphs
    Hongliang Lu
    Zixuan Yang
    Graphs and Combinatorics, 2023, 39
  • [7] Graphs with equal Grundy domination and independence number
    Bacso, Gabor
    Bresar, Bostjan
    Kuenzel, Kirsti
    Rall, Douglas F.
    DISCRETE OPTIMIZATION, 2023, 48
  • [8] Independence and matching number in graphs with maximum degree 4
    Joos, Felix
    DISCRETE MATHEMATICS, 2014, 323 : 1 - 6
  • [9] Matching Number, Independence Number, and Covering Vertex Number of Γ (Zn)
    AbuHijleh, Eman
    Abudayah, Mohammad
    Alomari, Omar
    Al-Ezeh, Hasan
    MATHEMATICS, 2019, 7 (01):
  • [10] ON THE MATCHING NUMBER AND THE INDEPENDENCE NUMBER OF A RANDOM INDUCED SUBHYPERGRAPH OF A HYPERGRAPH
    Lee, Sang June
    BULLETIN OF THE KOREAN MATHEMATICAL SOCIETY, 2018, 55 (05) : 1523 - 1528
12345