2025/06/10 by Lingjuan Shi, Wei Li, Shi, Lingjuan +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2506.08557
openalex publication_date 2025/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Ψ(G). In this paper, an algorithm to count Ψ(T) for a tree T is given. We show that for any tree T with n vertices, Ψ(T)≥\lceil(n)/(2)\rceil, and the tree which obtained the lower bound is characterized.