The Number of Independent Sets in a Regular Graph

Details The Number of Independent Sets in a Regular Graph The Number of Independent Sets in a Regular Graph

2009-09-18

arxiv.org/abs/0909.3354v1

Combinatorics, Probability and Computing, 19 (2010), No. 2, 315-320

Mathematics

Combinatorics

5 pages. Accepted by Combin. Probab. Comput

Scientific paper

10.1017/S0963548309990538

We show that the number of independent sets in an N-vertex, d-regular graph is at most (2^{d+1} - 1)^{N/2d}, where the bound is sharp for a disjoint union of complete d-regular bipartite graphs. This settles a conjecture of Alon in 1991 and Kahn in 2001. Kahn proved the bound when the graph is assumed to be bipartite. We give a short proof that reduces the general case to the bipartite case. Our method also works for a weighted generalization, i.e., an upper bound for the independence polynomial of a regular graph.

Affiliated with

Also associated with

No associations

Rating

The Number of Independent Sets in a Regular Graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Number of Independent Sets in a Regular Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Number of Independent Sets in a Regular Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-276250