Extremal hexagonal chains concerning k-matchings and k-independent sets

被引：0
|
作者：
Lian-zhu Zhang
Fu-ji Zhang
机构：
[1] Zhangzhou Teachers College,Department of Mathematics
[2] Zhangzhou,Department of Mathematics
[3] Xiamen University,undefined
[4] Xiamen,undefined
来源：
Journal of Mathematical Chemistry | 2000年 / 27卷
关键词：
hexagonal chain; graph; invariants; benzenoid hydrocarbons; -matching; -independent set;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Denote by ℬn the set of the hexagonal chains with n hexagons. For any Bn∈ℬn, let mk(Bn) and ik(Bn) be the numbers of k-matchings and k-independent sets of Bn, respectively. In the paper, we show that for any hexagonal chain Bn∈ℬn and for any k≥0, mk(Ln)≤mk(Bn)≤mk(Zn) and ik(Ln)≥ik(Bn)≥ik(Zn), with left equalities holding for all k only if Bn=Ln, and the right equalities holding for all k only if Bn=Zn, where Ln and Zn are the linear chain and the zig-zag chain, respectively. These generalize some related results known before.
引用
收藏
页码：319 / 329
页数：10
相关论文
共 23 条
  • [11] Maximum weight k-independent set problem on permutation graphs
    Saha, A
    Pal, M
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2003, 80 (12) : 1477 - 1487
  • [12] Remarks on k-Clique, k-Independent Set and 2-Contamination in Complementary Prisms
    Camargo, Priscila P.
    Souza, Ueverton S.
    Nascimento, Julliano R.
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2021, 32 (01) : 37 - 52
  • [13] Trees with extremal numbers of k-dominating sets
    Taletskii, D. S.
    DISCRETE MATHEMATICS, 2022, 345 (01)
  • [14] An efficient algorithm for finding a maximum weight k-independent set on trapezoid graphs
    Hota, M
    Pal, M
    Pal, TK
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2001, 18 (01) : 49 - 62
  • [15] Inductive k-independent graphs and c-colorable subgraphs in scheduling: a review
    Bentert, Matthias
    van Bevern, Rene
    Niedermeier, Rolf
    JOURNAL OF SCHEDULING, 2019, 22 (01) : 3 - 20
  • [16] A sequential algorithm for finding a maximum weight K-independent set on interval graphs
    Pal, M
    Bhattacharjee, GP
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1996, 60 (3-4) : 205 - 214
  • [17] An Efficient Algorithm for Finding a Maximum Weight k-Independent Set on Trapezoid Graphs
    Mrinmoy Hota
    Madhumangal Pal
    Tapan K. Pal
    Computational Optimization and Applications, 2001, 18 : 49 - 62
  • [18] Neighbourhoods of independent sets for (a, b, k)-critical graphs
    Zhou, Sizhong
    Xu, Yang
    BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 2008, 77 (02) : 277 - 283
  • [19] On the number of independent and k-dominating sets in graphs with average vertex degree at most k
    Taletskii, D. S.
    SBORNIK MATHEMATICS, 2023, 214 (11) : 1627 - 1650
  • [20] Maximizing the number of independent sets of fixed size in K n-covered graphs
    Wang, Anyao
    Hou, Xinmin
    Liu, Boyuan
    Ma, Yue
    JOURNAL OF GRAPH THEORY, 2022, 99 (02) : 175 - 185
123