2014/09/27 by Kang, Dong Yeap, Kim, Jaehoon, Kim, Younjin +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1409.7795
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. A 2-matching is also called an induced matching. In this paper, we estimate the maximum number of r-matchings in a tree of fixed order. We also prove that the n-vertex path has the maximum number of induced matchings among all n-vertex trees.