On the maximal matchings of trees

Abstract

An independent edge set of graph $G$ is a matching, and is maximal if it is not a proper subset of any other matching of $G$. The number of all the maximal matchings of $G$ is denoted by $\Psi (G)$. In this paper, an algorithm to count $\Psi (T)$ for a tree $T$ is given. We show that for any tree $T$ with $n$ vertices, $\Psi (T)\ge \lceil \frac{n}{2}\rceil$, and the tree which obtained the lower bound is characterized.

14 pages