On the number of independent sets in a tree

被引：0

作者：

Law, Hiu-Fai ^{[1
]}

机构：

[1] Univ Oxford, Inst Math, Oxford OX1 3LB, England

来源：

ELECTRONIC JOURNAL OF COMBINATORICS | 2010年 / 17卷 / 01期

关键词：

GRAPHS;

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We show in a simple way that for any k, m is an element of N, there exists a tree T such that the number of independent sets of T is congruent to k modulo m. This resolves a conjecture of Wagner (Almost all trees have an even number of independent sets, Electron. J. Combin. 16 (2009), #R93).

引用

页数：5

共 50 条

[1] ON THE NUMBER OF INDEPENDENT SETS OF NODES IN A TREE
DUTTON, R
CHANDRASEKHARAN, N
BRIGHAM, R
FIBONACCI QUARTERLY, 1993, 31 (02): : 98 - 104
[2] THE NUMBER OF MAXIMAL INDEPENDENT SETS IN A TREE
WILF, HS
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (01): : 125 - 130
[3] NOTE ON NUMBER OF MAXIMAL INDEPENDENT SETS IN A TREE
SANDERS, EL
NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, 1975, 22 (05): : A509 - A509
[4] An upper bound on the number of independent sets in a tree
Pedersen, Anders Sune
Vestergaard, Preben Dahl
ARS COMBINATORIA, 2007, 84 : 85 - 96
[5] Quasi-tree graphs with the largest number of maximal independent sets
Lin, Jenq-Jong
ARS COMBINATORIA, 2010, 97 : 27 - 32
[6] Dominating Sets and Independent Sets in a Tree
Jou, Min-Jen
ARS COMBINATORIA, 2010, 96 : 499 - 503
[7] Quasi-tree graphs with the second largest number of maximal independent sets
Lin, Jenq-Jong
ARS COMBINATORIA, 2013, 108 : 257 - 267
[8] The Number of Independent Sets in Graphs
Sapozhenko, A. A.
MOSCOW UNIVERSITY MATHEMATICS BULLETIN, 2007, 62 (03) : 116 - 118
[9] On the number of independent sets in expanders
Sapozhenko, A.A.
Discrete Mathematics and Applications, 2001, 11 (02): : 155 - 161
[10] On the number of independent sets in graphs with fixed independence number
Daynyak, A. B.
DISCRETE MATHEMATICS AND APPLICATIONS, 2007, 17 (03): : 249 - 252

← 1 2 3 4 5 →