On the number of independent sets in a tree

MaRDI QIDQ976671zbMATH OpenFDO

Authors Hiu Fai Law

Publication date 16 June 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/223159, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1n18.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

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

Review text

Summary: We show in a simple way that for any \(k, m \in \mathbb 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 \textit{S. G. Wagner} [Electron. J. Comb. 16, No. 1, Research Paper R93, 10 p. (2009; Zbl 1230.05165)].

Recommendations

• scientific article; zbMATH DE number 179305
• On the number of independent sets in the trees of a fixed diameter
• The Number of Maximal Independent Sets in a Tree
• On independent \([1, 2]\)-sets in trees
• On the number of independent subsets in trees with restricted degrees
• A Note on Independent Sets in Trees
• The structure and maximum number of maximum independent sets in trees
• Independent sets in trees
• Counting independent sets up to the tree threshold
• On the independent set sequence of a tree

Cited in

(22)

• On subgraph number independence in trees
• Closed formulas for the numbers of small independent sets and matchings and an extremal problem for trees
• On the number of maximal independent sets in complete \(q\)-ary trees
• A note on the number of matchings and independent sets in trees
• On the asymptotic behavior of the independence number of a random (n,n)-tree
• Trees of diameter 6 and 7 with minimum number of independent sets
• On the independence number of some random trees
• Almost all trees have an even number of independent sets
• The number of maximal independent sets of \((k+1)\)-valent trees
• On S₀-free forests with man independent sets
• A Note on Independent Sets in Trees
• On generalized independent subsets of trees
• scientific article; zbMATH DE number 32144 (Why is no real title available?)
• scientific article; zbMATH DE number 179305 (Why is no real title available?)
• On the number of F-matchings in a tree
• scientific article; zbMATH DE number 1735713 (Why is no real title available?)
• Independent sets in graphs
• On the number of independent sets in cycle-separated tricyclic graphs
• The maximum number of maximum dissociation sets in trees
• Minimum number of maximal dissociation sets in trees
• Asymptotic behavior of a generalized independent sets model on the two-dimensional Sierpinski gasket
• The number of independent sets in bipartite graphs and benzenoids

This page was built for publication: On the number of independent sets in a tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976671)