On the Number of $r$-Matchings in a Tree

Abstract

An $r$-matching in a graph $G$ is a collection of edges in $G$ such that the distance between any two edges is at least $r$. This generalizes both matchings and induced matchings as matchings are $1$-matchings and induced matchings are $2$-matchings. In this paper, we study the minimum and maximum number of $r$-matchings in a tree with fixed order.