go-v.orgdoi

On the Number of Independent Sets in a Tree

Hiu-Fai Law · The Electronic Journal of Combinatorics · 2010

  • DOI 10.37236/467
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2010

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2010

Abstract

We show in a simple way that for any $k,m\in{\Bbb 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).

Open the resolved locator · 10.37236/467

Metadata licence: OpenAlex metadata (CC0)