Trees with a given number of leaves and the maximal number of maximum independent sets

被引：0

作者：

Taletskii, Dmitriy S. ^{[1
]}

Malyshev, Dmitriy S. ^{[2
]}

机构：

[1] Lobachevsky State Univ Nizhny Novgorod, Nizhnii Novgorod, Russia

[2] Natl Res Univ Higher Sch Econ, Moscow, Russia

来源：

DISCRETE MATHEMATICS AND APPLICATIONS | 2021年 / 31卷 / 02期

关键词：

independent set; maximum independent set; maximal independent set; extremal tree; GRAPHS; INDEX;

D O I：

10.1515/dma-2021-0012

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A complete description of trees with maximal possible number of maximum independent sets among all n-vertex trees with exactly l leaves is obtained. For all values of the parameters n and l the extremal tree is unique and is the result of merging the endpoints of l simple paths.

引用

页码：135 / 144

页数：10

共 20 条

[1]

[Anonymous], 2007, INT J NONLIN SCI

[2]

Dainyak AB., 2010, J APPL IND MATH, V4, P163, DOI DOI 10.1134/S1990478910020043

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

Hanyuan D., 2008, MATCH-COMMUN MATH CO, V60, P601

[5] Maximizing the number of independent subsets over trees with bounded degree [J].

Heuberger, Clemens ;

Wagner, Stephan G. .

JOURNAL OF GRAPH THEORY, 2008, 58 (01) :49-68

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

HOPKINS, G ;

STATON, W .

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

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

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

Jou, MJ ;

Chang, GJ .

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

[9] The number of maximum independent sets in graphs [J].

Jou, MJ ;

Chang, GJ .

TAIWANESE JOURNAL OF MATHEMATICS, 2000, 4 (04) :685-695

[10] Graphs, partitions and Fibonacci numbers [J].

Knopfmacher, Arnold ;

Tichy, Robert F. ;

Wagner, Stephan ;

Ziegler, Volker .

DISCRETE APPLIED MATHEMATICS, 2007, 155 (10) :1175-1187

← 1 2 →