Graphs with the second largest number of maximal independent sets

被引：19

作者：

Jin, Zemin ^{[1
]}

Li, Xueliang ^{[2
,3
]}

机构：

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

[2] Nankai Univ, Ctr Combinator, Tianjin 300071, Peoples R China

[3] Nankai Univ, LPMC, Tianjin 300071, Peoples R China

来源：

DISCRETE MATHEMATICS | 2008年 / 308卷 / 23期

基金：

中国国家自然科学基金;

关键词：

Maximal (maximum) independent set; Extremal graph;

D O I：

10.1016/j.disc.2007.10.032

中图分类号：

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. Erdos and Moser raised the problem of determining the maximum value of mi(G) among all graphs of order it and the extremal graphs achieving this maximum value. This problem was solved by Moon and Moser. Then it was studied for many special classes of graphs, including trees, forests, bipartite graphs, connected graphs, (connected) triangle-free graphs, (connected) graphs with at most one cycle, and recently, (connected) graphs with at most r cycles. In this paper we determine the second largest value of mi(G) and xi(G) among all graphs of order it. Moreover, the extremal graphs achieving these values are also determined. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：5864 / 5870

页数：7

共 23 条

[1]

Bondy J.A., 2008, GRAD TEXTS MATH

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