On the maximum number of maximum independent sets in connected graphs

被引：7

作者：

Mohr, Elena ^{[1
]}

Rautenbach, Dieter ^{[1
]}

机构：

[1] Univ Ulm, Inst Optimierung & Operat Res, Ulm, Germany

来源：

JOURNAL OF GRAPH THEORY | 2021年 / 96卷 / 04期

关键词：

maximum independent set; Turan graph;

D O I：

10.1002/jgt.22629

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We characterize the connected graphs of given ordernand given independence number alpha that maximize the number of maximum independent sets. For3 <=alpha <= n/2, there is a unique such graph that arises from the disjoint union of alpha cliques of orders left ceiling n alpha right ceiling andLn alpha<SIC> RIGHT FLOOR, which is the complement of a Turan graph, by selecting a vertexxin a largest clique and adding an edge betweenxand a vertex in each of the remaining alpha-1cliques. Our result confirms a conjecture of Derikvand and Oboudi.

引用

页码：510 / 521

页数：12

共 9 条

[1]

Derikvand T, 2014, TRANS COMB, V3, P29

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

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

Jou, MJ ;

Chang, GJ .

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

[4] On the Maximum Number of Maximum Independent Sets [J].

Mohr, E. ;

Rautenbach, D. .

GRAPHS AND COMBINATORICS, 2018, 34 (06) :1729-1740

[5] ON CLIQUES IN GRAPHS [J].

MOON, JW ;

MOSER, L .

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

[6] Maximal and maximum independent sets in graphs with at most r cycles [J].

Sagan, Bruce E. ;

Vatter, Vincent R. .

JOURNAL OF GRAPH THEORY, 2006, 53 (04) :283-314

[7]

Turan P., 1941, Mat. Fiz. Lapok, V48, P436

[8] THE STRUCTURE AND MAXIMUM NUMBER OF MAXIMUM INDEPENDENT SETS IN TREES [J].

ZITO, J .

JOURNAL OF GRAPH THEORY, 1991, 15 (02) :207-221

[9]

Zykov A.A., 1949, Mat. Sb., V66, P163

← 1 →