For graphs F and G an F-matching in G is a subgraph of G consisting of pairwise vertex disjoint copies of F. The number of F-matchings in G is denoted by s(F,G). We show that for every fixed positive integer m and every fixed tree F, the probability that s(F, Tn) ≡ 0 (mod m), where Tn is a random labeled tree with n vertices, tends to one exponentially fast as n grows to infinity. A similar result is proven for induced F-matchings. As a very special special case this implies that the number of independent sets in a random labeled tree is almost surely a zero residue. A recent result of Wagner shows that this is the case for random unlabeled trees as well.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics