The second largest number of maximal independent sets in connected graphs with at most one cycle

被引：0
作者：
Min-Jen Jou
机构：
[1] Ling Tung University,
来源：
Journal of Combinatorial Optimization | 2012年 / 24卷
关键词：
Maximal independent set; Cycle; Clasp;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we determine the second largest number of maximal independent sets among all graphs (respectively, connected graphs) of order n≥4 with at most one cycle. We also characterize those extremal graphs achieving these values.
引用
收藏
页码：192 / 201
页数：9
相关论文
共 28 条
  • [1] Alzoubi K(2003)Maximal independent set, weakly-connected dominating set, and induced spanners in wireless ad hoc networks Int J Found Comput Sci 14 287-303
  • [2] Wan P-J(1988)Binomial-combinatorial properties of Clar structures Discrete Appl Math 19 145-156
  • [3] Frieder O(1993)The number of maximal independent sets in triangle-free graphs SIAM J Discrete Math 6 284-288
  • [4] El-Basil S(2008)Graphs with the second largest number of maximal independent sets Discrete Math 308 5864-5870
  • [5] Hujter M(1997)Maximal independent sets in graphs with at most one cycle Discrete Appl Math 79 67-73
  • [6] Tuza Z(2002)Algorithmic aspects of counting independent sets Ars Comb 65 265-277
  • [7] Jin Z(2009)Trees with the second largest number of maximal independent sets Discrete Math 309 4469-4474
  • [8] Li X(2007)Graphs, partitions and Fibonacci numbers Discrete Appl Math 155 1175-1187
  • [9] Jou MJ(1965)On cliques in graphs Isr J Math 3 23-28
  • [10] Chang GJ(2003)CLIP: similarity searching of 3D databases using clique detection J Chem Inf Comput Sci 43 443-448
123