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 条
  • [31] Fixed points and maximal independent sets in AND-OR networks
    Aracena, J
    Demongeot, J
    Goles, E
    DISCRETE APPLIED MATHEMATICS, 2004, 138 (03) : 277 - 288
  • [32] Trees with the second largest number of maximal independent sets
    Jou, Min-Jen
    Lin, Jenq-Jong
    DISCRETE MATHEMATICS, 2009, 309 (13) : 4469 - 4474
  • [33] Rounds vs Communication Tradeoffs for Maximal Independent Sets
    Assadi, Sepehr
    Kol, Gillat
    Zhang, Zhijun
    2022 IEEE 63RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2022, : 1193 - 1204
  • [34] Hitting All Maximal Independent Sets of a Bipartite Graph
    Cardinal, Jean
    Joret, Gwenael
    ALGORITHMICA, 2015, 72 (02) : 359 - 368
  • [35] Hitting All Maximal Independent Sets of a Bipartite Graph
    Jean Cardinal
    Gwenaël Joret
    Algorithmica, 2015, 72 : 359 - 368
  • [36] Enumerating maximal independent sets with applications to graph colouring
    Byskov, JM
    OPERATIONS RESEARCH LETTERS, 2004, 32 (06) : 547 - 556
  • [37] Cycle-maximal triangle-free graphs
    Durocher, Stephane
    Gunderson, David S.
    Li, Pak Ching
    Skala, Matthew
    DISCRETE MATHEMATICS, 2015, 338 (02) : 274 - 290
  • [38] The shortest cycle having the maximal number of coalition graphs
    Dobrynin, Andrey A.
    Golmohammadi, Hamidreza
    DISCRETE MATHEMATICS LETTERS, 2024, 14 : 21 - 26
  • [39] Distributed Independent Sets in Interval and Segment Intersection Graphs
    Gorain, Barun
    Mondal, Kaushik
    Pandit, Supantha
    SOFSEM 2021: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2021, 12607 : 175 - 188
  • [40] Rainbow independent sets in graphs with maximum degree two
    Ma, Yue
    Hou, Xinmin
    Gao, Jun
    Liu, Boyuan
    Yin, Zhi
    DISCRETE APPLIED MATHEMATICS, 2022, 317 : 101 - 108
12345