Independent sets in graphs with given minimum degree

James Alexander, Jonathan Cutler, Tim Mink

Research output: Contribution to journalArticleResearchpeer-review

10 Citations (Scopus)

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 languageEnglish
JournalElectronic Journal of Combinatorics
Volume19
Issue number3
StatePublished - 27 Sep 2012

Fingerprint

Minimum Degree
Independent Set
Entropy
Graph in graph theory
Regular Graph
Bipartite Graph
Enumeration
Trivial
Cover
Restriction

Cite this

@article{29af5cf575aa4acfb89cf5a7b4aca379,
title = "Independent sets in graphs with given minimum degree",
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δ.",
author = "James Alexander and Jonathan Cutler and Tim Mink",
year = "2012",
month = "9",
day = "27",
language = "English",
volume = "19",
journal = "Electronic Journal of Combinatorics",
issn = "1077-8926",
publisher = "Electronic Journal of Combinatorics",
number = "3",

}

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

In: Electronic Journal of Combinatorics, Vol. 19, No. 3, 27.09.2012.

Research output: Contribution to journalArticleResearchpeer-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 -