THE SECOND LARGEST NUMBER OF MAXIMAL INDEPENDENT SETS IN GRAPHS WITH AT MOST k CYCLES

被引：1

作者：

Jin, Zemin ^{[1
]}

Yan, Sherry H. F. ^{[1
]}

机构：

[1] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Peoples R China

来源：

TAIWANESE JOURNAL OF MATHEMATICS | 2009年 / 13卷 / 05期

关键词：

Maximal independent sets; Extremal graphs; TREES;

D O I：

10.11650/twjm/1500405548

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a simple undirected graph. Denote by mi(G) (respectively, xi(G)) the number of maximal (respectively, maximum) independent sets in G. In this paper we deter-mine the second largest value of mi(G) for graphs with at most k cycles. Extremal graphs achieving these values are also determined.

引用

页码：1397 / 1410

页数：14

共 27 条

[1]

Bondy J. A., 1976, Graduate Texts in Mathematics, V290

[2]

Chang GJ, 1999, DISCRETE MATH, V197, P169

[3] The cardinality of the collection of maximum independent sets of a functional graph [J].

Chang, SC ;

Yeh, YN .

ADVANCES IN APPLIED MATHEMATICS, 1997, 18 (03) :286-299

[4]

FABER M, 1993, NETWORKS, V23, P207

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

FUREDI, Z .

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

[6]

Griggs J. R., 1986, UNPUB

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

[8] THE MAXIMUM NUMBER OF CLIQUES IN DENSE GRAPHS [J].

HEDMAN, B .

DISCRETE MATHEMATICS, 1985, 54 (02) :161-166

[9] GRAPHS WITH UNIQUE MAXIMUM INDEPENDENT SETS [J].

HOPKINS, G ;

STATON, W .

DISCRETE MATHEMATICS, 1985, 57 (03) :245-251

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

← 1 2 3 →