Bounds on the number of vertex independent sets in a graph

被引：15

作者：

Pedersen, Anders Sune ^{[1
]}

Vestergaard, Preben Dahl ^{[1
]}

机构：

[1] Aalborg Univ, Dept Math, DK-9220 Aalborg, Denmark

来源：

TAIWANESE JOURNAL OF MATHEMATICS | 2006年 / 10卷 / 06期

关键词：

independent sets; Merrifield-Simmons; Hoyosa; Fibonacci number; claw-free raphs; unicyclic graphs; bipartite graphs;

D O I：

10.11650/twjm/1500404576

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We consider the number of vertex independent sets i(G). In general, the problem of determining the value of i(G) is NP-complete. We present several upper and lower bounds for i(G) in terms of order, size or independence number. We obtain improved bounds for i(G) on restricted graph classes such as the bipartite graphs, unicyclic graphs, regular graphs and claw-free graphs.

引用

页码：1575 / 1587

页数：13

共 22 条

[1]

[Anonymous], 1995, CHIN J MATH

[2]

Brandstadt A., 1999, SIAM MONOGRAPHS DISC

[3]

Chou M. J., 2000, TAIWAN J MATH, V4, P685

[4]

CHOU MJ, 1995, P 2 AS MATH C WORLD, P265

[5] THE NUMBER OF MAXIMAL INDEPENDENT SETS IN CONNECTED GRAPHS [J].

FUREDI, Z .

JOURNAL OF GRAPH THEORY, 1987, 11 (04) :463-470

[6] THE NUMBER OF MAXIMAL INDEPENDENT SETS IN A CONNECTED GRAPH [J].

GRIGGS, JR ;

GRINSTEAD, CM ;

GUICHARD, DR .

DISCRETE MATHEMATICS, 1988, 68 (2-3) :211-220

[7] TOPOLOGICAL INDEX - NEWLY PROPOSED QUANTITY CHARACTERIZING TOPOLOGICCAL NATURE OF STRUCTURAL ISOMERS OF SATURATED HYDROCARBONS [J].

HOSOYA, H .

BULLETIN OF THE CHEMICAL SOCIETY OF JAPAN, 1971, 44 (09) :2332-+

[8] THE NUMBER OF MAXIMAL INDEPENDENT SETS IN TRIANGLE-FREE GRAPHS [J].

HUJTER, M ;

TUZA, Z .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1993, 6 (02) :284-288

[9] A finiteness theorem for maximal independent sets [J].

Jou, MJ ;

Chang, GJ ;

Lin, C ;

Ma, TH .

GRAPHS AND COMBINATORICS, 1996, 12 (04) :321-326

[10] Maximal independent sets in graphs with at most one cycle [J].

Jou, MJ ;

Chang, GJ .

DISCRETE APPLIED MATHEMATICS, 1997, 79 (1-3) :67-73

← 1 2 3 →