The number of independent sets in unicyclic graphs

被引：72
作者：
Pedersen, AS [1 ]
Vestergaard, PD [1 ]
机构：
[1] Univ Aalborg, Dept Math, DK-9220 Aalborg, Denmark
来源：
DISCRETE APPLIED MATHEMATICS | 2005年 / 152卷 / 1-3期
关键词：
unicyclic graphs; independent sets; bounds; Fibonacci numbers;
D O I：
10.1016/j.dam.2005.04.002
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In this paper, we determine upper and lower bounds for the number of independent sets in a unicyclic graph in terms of its order. This gives an upper bound for the number of independent sets in a connected graph which contains at least one cycle. We also determine the upper bound for the number of independent sets in a unicyclic graph in terms of order and girth. In each case, we characterize the extremal graphs. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码：246 / 256
页数：11
相关论文
共 11 条
[1]  
Chou M. J., 2000, TAIWAN J MATH, V4, P685
[2]  
CHOU MJ, 1995, P 2 AS MATH C WORLD, P265
[3]   Maximal independent sets in graphs with at most one cycle [J].
Jou, MJ ;
Chang, GJ .
DISCRETE APPLIED MATHEMATICS, 1997, 79 (1-3) :67-73
[4]  
LIN SB, 1995, CHINESE J MATH, V32, P199
[5]  
Merrifield R.E., 1989, TOPOLOGICAL METHODS
[6]  
Miller R.E., 1960, RC240 IBM TJ WATS RE
[7]   ON CLIQUES IN GRAPHS [J].
MOON, JW ;
MOSER, L .
ISRAEL JOURNAL OF MATHEMATICS, 1965, 3 (01) :23-&
[8]  
PEDERSEN AS, UNPUB TAIWANESE J MA
[9]  
PEDERSEN AS, IN PRESS ARS COMBIN
[10]  
PRODINGER H, 1982, FIBONACCI QUART, V20, P16
12