A New Method for Enumerating Independent Sets of a Fixed Size in General Graphs

被引：6

作者：

Alexander, James ^{[1
]}

Mink, Tim ^{[2
]}

机构：

[1] Univ Delaware, Dept Math Sci, Newark, DE 19716 USA

[2] Montclair State Univ, Dept Math, Montclair, NJ 07043 USA

来源：

JOURNAL OF GRAPH THEORY | 2016年 / 81卷 / 01期

关键词：

independent sets; minimum degree; cliques; subgraph enumeration; extremal graph theory; regular graphs; Moore graphs; NUMBER;

D O I：

10.1002/jgt.21861

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We develop a new method for enumerating independent sets of a fixed size in general graphs, and we use this method to show that a conjecture of Engbers and Galvin [7] holds for all but finitely many graphs. We also use our method to prove special cases of a conjecture of Kahn [13]. In addition, we show that our method is particularly useful for computing the number of independent sets of small sizes in general regular graphs and Moore graphs, and we argue that it can be used in many other cases when dealing with graphs that have numerous structural restrictions. (C) 2015 Wiley Periodicals, Inc. J. Graph Theory 81: 57-72, 2016

引用

页码：57 / 72

页数：16

共 20 条

[1]

Alexander J, 2012, ELECTRON J COMB, V19

[2]

Babai L., 1992, Linear algebra methods in combinatorics

[3]

Bollobas B., 1986, Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability

[4]

Bollobas B., 1998, GRADUATE TEXTS ADV M