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 条
  • [31] On the independence number of graphs with maximum degree 3
    Kanj, Iyad
    Zhang, Fenghui
    THEORETICAL COMPUTER SCIENCE, 2013, 478 : 51 - 75
  • [32] ON THE INDEPENDENCE NUMBER OF EDGE CHROMATIC CRITICAL GRAPHS
    Pang, Shiyou
    Miao, Lianying
    Song, Wenyao
    Miao, Zhengke
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2014, 34 (03) : 577 - 584
  • [33] Local transformations of graphs preserving independence number
    Alekseev, VE
    Lozin, VV
    DISCRETE APPLIED MATHEMATICS, 2004, 135 (1-3) : 17 - 30
  • [34] On the independence transversal total domination number of graphs
    Cabrera Martinez, Abel
    Sigarreta Almira, Jose M.
    Yero, Ismael G.
    DISCRETE APPLIED MATHEMATICS, 2017, 219 : 65 - 73
  • [35] Embedding trees in graphs with independence number two
    Hu, Xiaolan
    Chen, Yaojun
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2018, 10 (04)
  • [36] Admissible Property of Graphs in Terms of Independence Number
    Hua, Hongbo
    Hua, Xinying
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2022, 45 (05) : 2123 - 2135
  • [37] A new lower bound on the independence number of graphs
    Angel, Eric
    Campigotto, Romain
    Laforest, Christian
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (06) : 847 - 852
  • [38] On the Connectivity and Independence Number of Power Graphs of Groups
    Peter J. Cameron
    Sayyed Heidar Jafari
    Graphs and Combinatorics, 2020, 36 : 895 - 904
  • [39] Independence Number and k-Trees of Graphs
    Yan, Zheng
    GRAPHS AND COMBINATORICS, 2017, 33 (05) : 1089 - 1093
  • [40] On the Structure of Hamiltonian Graphs with Small Independence Number
    Jedlickova, Nikola
    Kratochvil, Jan
    COMBINATORIAL ALGORITHMS, IWOCA 2024, 2024, 14764 : 180 - 192
12345