### Abstract

The enumeration of independent sets in graphs with various restrictions has been a topic of much interest of late. Let i(G) be the number of independent sets in a graph G and let i
_{t}(G) be the number of independent sets in G of size t. Kahn used entropy to show that if G is an r-regular bipartite graph with n vertices, then i(G) ≤ i(K
_{r,r})
^{n/2r}. Zhao used bipartite double covers to extend this bound to general r-regular graphs. Galvin proved that if G is a graph with δ(G) ≥ δ and n large enough, then i(G) ≤ i(K
_{δ,n-δ}). In this paper, we prove that if G is a bipartite graph on n vertices with δ(G) ≥ δ where n ≥ 2δ, then i
_{t}(G) ≤ i
_{t}(K
_{δ,n-δ}) when t ≥ 3. We note that this result cannot be extended to t = 2 (and is trivial for t = 0, 1). Also, we use Kahn's entropy argument and Zhao's extension to prove that if G is a graph with n vertices, δ(G) ≥ δ, and Δ(G) ≤ Δ, then i(G) ≤ i(K
_{δ;≥})
^{n/2δ}.

Original language | English |
---|---|

Journal | Electronic Journal of Combinatorics |

Volume | 19 |

Issue number | 3 |

State | Published - 27 Sep 2012 |

### Fingerprint

### Cite this

*Electronic Journal of Combinatorics*,

*19*(3).

}

*Electronic Journal of Combinatorics*, vol. 19, no. 3.

**Independent sets in graphs with given minimum degree.** / Alexander, James; Cutler, Jonathan; Mink, Tim.

Research output: Contribution to journal › Article › Research › peer-review

TY - JOUR

T1 - Independent sets in graphs with given minimum degree

AU - Alexander, James

AU - Cutler, Jonathan

AU - Mink, Tim

PY - 2012/9/27

Y1 - 2012/9/27

N2 - The enumeration of independent sets in graphs with various restrictions has been a topic of much interest of late. Let i(G) be the number of independent sets in a graph G and let i t(G) be the number of independent sets in G of size t. Kahn used entropy to show that if G is an r-regular bipartite graph with n vertices, then i(G) ≤ i(K r,r) n/2r. Zhao used bipartite double covers to extend this bound to general r-regular graphs. Galvin proved that if G is a graph with δ(G) ≥ δ and n large enough, then i(G) ≤ i(K δ,n-δ). In this paper, we prove that if G is a bipartite graph on n vertices with δ(G) ≥ δ where n ≥ 2δ, then i t(G) ≤ i t(K δ,n-δ) when t ≥ 3. We note that this result cannot be extended to t = 2 (and is trivial for t = 0, 1). Also, we use Kahn's entropy argument and Zhao's extension to prove that if G is a graph with n vertices, δ(G) ≥ δ, and Δ(G) ≤ Δ, then i(G) ≤ i(K δ;≥) n/2δ.

AB - The enumeration of independent sets in graphs with various restrictions has been a topic of much interest of late. Let i(G) be the number of independent sets in a graph G and let i t(G) be the number of independent sets in G of size t. Kahn used entropy to show that if G is an r-regular bipartite graph with n vertices, then i(G) ≤ i(K r,r) n/2r. Zhao used bipartite double covers to extend this bound to general r-regular graphs. Galvin proved that if G is a graph with δ(G) ≥ δ and n large enough, then i(G) ≤ i(K δ,n-δ). In this paper, we prove that if G is a bipartite graph on n vertices with δ(G) ≥ δ where n ≥ 2δ, then i t(G) ≤ i t(K δ,n-δ) when t ≥ 3. We note that this result cannot be extended to t = 2 (and is trivial for t = 0, 1). Also, we use Kahn's entropy argument and Zhao's extension to prove that if G is a graph with n vertices, δ(G) ≥ δ, and Δ(G) ≤ Δ, then i(G) ≤ i(K δ;≥) n/2δ.

UR - http://www.scopus.com/inward/record.url?scp=84867120323&partnerID=8YFLogxK

M3 - Article

VL - 19

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

SN - 1077-8926

IS - 3

ER -