Independence and matching number of some graphs

被引:0
|
作者
Ming Chen
Yusheng Li
Yiting Yang
机构
[1] Jiaxing University,College of Mathematics Physics and Information Engineering
[2] Tongji University,School of Mathematical Sciences
来源
Journal of Combinatorial Optimization | 2019年 / 37卷
关键词
Independence number; Matching number; Maximum degree;
D O I
暂无
中图分类号
学科分类号
摘要
For a graph G, let n(G), α(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha (G)$$\end{document} and β(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta (G)$$\end{document} be its order, independence number and matching number, respectively. We showed that Δ(G)+k4α(G)+β(G)≥n(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{\Delta (G)+k}{4}\alpha (G) + \beta (G) \ge n(G)$$\end{document} for some Kk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_k$$\end{document}-free graph G with Δ(G)≥k-1≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta (G)\ge k-1\ge 2$$\end{document}.
引用
收藏
页码:1342 / 1350
页数:8
相关论文
共 50 条
  • [1] Independence and matching number of some graphs
    Chen, Ming
    Li, Yusheng
    Yang, Yiting
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 37 (04) : 1342 - 1350
  • [2] Regular graphs with equal matching number and independence number
    Yang, Zixuan
    Lu, Hongliang
    DISCRETE APPLIED MATHEMATICS, 2022, 310 : 86 - 90
  • [3] Cubic graphs with equal independence number and matching number
    Mohr, Elena
    Rautenbach, Dieter
    DISCRETE MATHEMATICS, 2021, 344 (01)
  • [4] Independence and matching number in graphs with maximum degree 4
    Joos, Felix
    DISCRETE MATHEMATICS, 2014, 323 : 1 - 6
  • [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] Matching Number, Independence Number, and Covering Vertex Number of Γ (Zn)
    AbuHijleh, Eman
    Abudayah, Mohammad
    Alomari, Omar
    Al-Ezeh, Hasan
    MATHEMATICS, 2019, 7 (01):
  • [8] Some results on the independence number of connected domination critical graphs
    Kaemawichanurat, P.
    Jiarasuksakun, T.
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2018, 15 (02) : 190 - 196
  • [9] 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
  • [10] On the strength and independence number of graphs
    Ichishima, Rikio
    Muntaner-Batle, Francesc A.
    Takahashi, Yukio
    CONTRIBUTIONS TO MATHEMATICS, 2022, 6 : 25 - 29