### Abstract

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, T_{n}) ≡ 0 (mod m), where T_{n} 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.

Original language | English (US) |
---|---|

Journal | Electronic Journal of Combinatorics |

Volume | 18 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 2011 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'The number of F-matchings in almost every tree is a zero residue'. Together they form a unique fingerprint.

## Cite this

*Electronic Journal of Combinatorics*,

*18*(1). https://doi.org/10.37236/517