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

Dong Yeap Kang, Jaehoon Kim, Younjin Kim, Hiu-Fai Law

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.


Keywords


Matching, Independent set, Tree

Full Text: PDF