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

共 9 条

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

FUREDI, Z .

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

[2]

Griggs J. R., 1986, UNPUB

[3] 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

[4] 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

[5]

Jou M.J., 1991, THESIS NATL CENTRAL

[6] MAXIMAL INDEPENDENT SETS IN BIPARTITE GRAPHS [J].

LIU, JQ .

JOURNAL OF GRAPH THEORY, 1993, 17 (04) :495-507

[7] ON CLIQUES IN GRAPHS [J].

MOON, JW ;

MOSER, L .

ISRAEL JOURNAL OF MATHEMATICS, 1965, 3 (01) :23-&

[8]

Sagan B., 1988, SIAM J DISCRETE MATH, V1, P105

[9] THE NUMBER OF MAXIMAL INDEPENDENT SETS IN A TREE [J].

WILF, HS .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (01) :125-130

← 1 →