On the Number of Independent Sets in a Tree

descriptionPublicationkeyboard_double_arrow_right Article 22 Mar 2010Publisher:The Electronic Journal of CombinatoricsJournal:The Electronic Journal of Combinatorics, volume 17 (eissn: 1077-8926,

Copyright policy )

Authors: Hiu-Fai Law;

doi: 10.37236/467

On the Number of Independent Sets in a Tree

- Summary
- Subjects
- Metrics

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).

Related Organizations

University of Oxford
United Kingdom

Keywords

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Trees

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	8
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average

Found an issue? Give us feedback

8

Average

gold

Fields of Science (3) View all

Fields of Science

Related to Research communities

UArctic