Independent sets in graphs

被引：7
作者：
Dainyak, Aleksandr B. [1 ]
Sapozhenko, Aleksandr A. [2 ]
机构：
[1] Moscow Inst Phys & Technol, Moscow, Russia
[2] Moscow MV Lomonosov State Univ, Moscow, Russia
来源：
DISCRETE MATHEMATICS AND APPLICATIONS | 2016年 / 26卷 / 06期
基金：
俄罗斯基础研究基金会;
关键词：
independent sets; domination; enumeration; extremal graph theory;
D O I：
10.1515/dma-2016-0028
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We give a survey of the enumeration of independent sets in graphs and of some related problems.
引用
收藏
页码：323 / 346
页数：24
相关论文
共 186 条
[1]   Finding independent sets in a graph using continuous multivariable polynomial formulations [J].
Abello, J ;
Butenko, S ;
Pardalos, PM ;
Resende, MGC .
JOURNAL OF GLOBAL OPTIMIZATION, 2001, 21 (02) :111-137
[2]   A NOTE ON RAMSEY NUMBERS [J].
AJTAI, M ;
KOMLOS, J ;
SZEMEREDI, E .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1980, 29 (03) :354-360
[3]  
Alavi Y., 1987, C NUMER, V58, P15
[4]   An upper bound for the number of maximal independent sets in a graph [J].
Alekseev, V. E. .
DISCRETE MATHEMATICS AND APPLICATIONS, 2007, 17 (04) :355-359
[5]   Augmenting graphs for independent sets [J].
Alekseev, VE ;
Lozin, VV .
DISCRETE APPLIED MATHEMATICS, 2004, 145 (01) :3-10
[6]   Polynomial algorithm for finding the largest independent sets in graphs without forks [J].
Alekseev, VE .
DISCRETE APPLIED MATHEMATICS, 2004, 135 (1-3) :3-16
[7]   Independent sets of maximum weight in (p, q)-colorable graphs [J].
Alekseev, VE ;
Lozin, VV .
DISCRETE MATHEMATICS, 2003, 265 (1-3) :351-356
[8]   The Shannon capacity of a graph and the independence numbers of its powers [J].
Alon, N ;
Lubetzky, E .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (05) :2172-2176
[9]   The Shannon capacity of a union [J].
Alon, N .
COMBINATORICA, 1998, 18 (03) :301-310
[10]  
Alon N, 1996, RANDOM STRUCT ALGOR, V9, P271, DOI 10.1002/(SICI)1098-2418(199610)9:3<271::AID-RSA1>3.0.CO
12345678910