A sharp upper bound for the number of stable sets in graphs with given number of cut edges

被引：13

作者：

Hua, Hongbo ^{[1
,2
,3
]}

机构：

[1] NW Polytech Univ, Dept Appl Math, Xian 710072, Shaanxi, Peoples R China

[2] Huaiyin Inst Technol, Dept Comp Sci, Huaian 223003, Jiangsu, Peoples R China

[3] Huaiyin Inst Technol, Inst Appl Math, Huaian 223003, Jiangsu, Peoples R China

来源：

APPLIED MATHEMATICS LETTERS | 2009年 / 22卷 / 09期

关键词：

Stable set; Cut edge; 2-edge-connected graph; Upper bound; Extremal graph; FIBONACCI NUMBERS; INDEPENDENT SETS; INDEXES; TREES;

D O I：

10.1016/j.aml.2009.03.011

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let G be a connected and simple graph, and let i(G) denote the number of stable sets in G. In this letter, we have presented a sharp upper bound for the i(G)-value among the set of graphs with k cut edges for all possible values of k, and characterized the corresponding extremal graphs as well. (C) 2009 Elsevier Ltd. All rights reserved.

引用

页码：1380 / 1385

页数：6

共 18 条

[1]

Alameddine AF, 1998, FIBONACCI QUART, V36, P206

[2]

Gutman I., 1990, Coll. Sci. Pap. Fac. Sci. Kragujevac, V11, P11

[3]

Gutman I., 2012, MATH CONCEPTS ORGANI

[4]

Gutman I., 1992, PUBL I MATH BEOGRAD, V52, P5

[5]

HUA H, CACTI GIVEN PE UNPUB

[6]

LI X, 1996, AUSTRALASIAN J COMB, V14, P15

[7]

Li X., 2005, MATCH COMMUN MATH CO, V54

[8] The inverse problems for some topological indices in combinatorial chemistry [J].

Li, XL ;

Li, ZM ;

Wang, LS .

JOURNAL OF COMPUTATIONAL BIOLOGY, 2003, 10 (01) :47-55

[9]

Lin C., 1995, CHIN J MATH, V23, P199

[10] BIPARTITE GRAPHS CAN HAVE ANY NUMBER OF INDEPENDENT SETS [J].

LINEK, V .

DISCRETE MATHEMATICS, 1989, 76 (02) :131-136

← 1 2 →