Maximal independent sets in graphs with at most one cycle

被引：35
作者：
Jou, MJ [1 ]
Chang, GJ [1 ]
机构：
[1] NATL CHIAO TUNG UNIV,DEPT MATH APPL,HSINCHU 30050,TAIWAN
来源：
DISCRETE APPLIED MATHEMATICS | 1997年 / 79卷 / 1-3期
关键词：
(maximal) independent set; cycle; connected graph; isolated vertex; leaf; baton;
D O I：
10.1016/S0166-218X(97)00033-4
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper, we determine the largest number of maximal independent sets among all connected graphs of order n, which contain at most one cycle. We also characterize those extremal graphs achieving this maximum value. As a consequence, the corresponding results for graphs with at most one cycle but not necessarily connected are also given.
引用
收藏
页码：67 / 73
页数：7
相关论文
共 50 条
  • [41] Maximal Independent Sets in Heterogeneous Wireless Ad Hoc Networks
    Bai, Sen
    Che, Xiangjiu
    Bai, Xin
    Wei, Xiaohui
    IEEE TRANSACTIONS ON MOBILE COMPUTING, 2016, 15 (08) : 2023 - 2033
  • [42] Maximal Independent Sets in Heterogeneous Wireless Ad Hoc Networks
    Bai S.
    Che X.
    Bai X.
    Wei X.
    Che, Xiangjiu (chexj@jlu.edu.cn), 2023, Institute of Electrical and Electronics Engineers Inc., United States (15): : 2023 - 2033
  • [43] On the Maximal Independent Sets of k-mers with the Edit Distance
    Ma, Leran
    Chen, Ke
    Shao, Mingfu
    14TH ACM CONFERENCE ON BIOINFORMATICS, COMPUTATIONAL BIOLOGY, AND HEALTH INFORMATICS, BCB 2023, 2023,
  • [44] The number of maximal independent sets in trees with a given number of leaves
    Taletskii, D. S.
    Malyshev, D. S.
    DISCRETE APPLIED MATHEMATICS, 2022, 314 : 321 - 330
  • [45] The number of maximal independent sets of (k + 1)-valent trees
    Song J.
    Han H.
    Lee C.
    Journal of Applied Mathematics and Computing, 2006, 21 (1-2) : 315 - 324
  • [46] Random maximal independent sets and the unfriendly theater seating arrangement problem
    Georgiou, Konstantinos
    Kranakis, Evangelos
    Krizanc, Danny
    DISCRETE MATHEMATICS, 2009, 309 (16) : 5120 - 5129
  • [47] Fixed points in conjunctive networks and maximal independent sets in graph contractions
    Aracena, Julio
    Richard, Adrien
    Salinas, Lilian
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2017, 88 : 145 - 163
  • [48] An optimal maximal independent set algorithm for bounded-independence graphs
    Johannes Schneider
    Roger Wattenhofer
    Distributed Computing, 2010, 22 : 349 - 361
  • [49] An optimal maximal independent set algorithm for bounded-independence graphs
    Schneider, Johannes
    Wattenhofer, Roger
    DISTRIBUTED COMPUTING, 2010, 22 (5-6) : 349 - 361
  • [50] Trees with extremal numbers of maximal independent sets including the set of leaves
    Wloch, Iwona
    DISCRETE MATHEMATICS, 2008, 308 (20) : 4768 - 4772
12345