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

  • Dong Yeap Kang
  • Jaehoon Kim
  • Younjin Kim
  • Hiu-Fai Law
Keywords: Matching, Independent set, 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.

Published
2017-02-03
Article Number
P1.24