On the maximal matchings of trees
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915335308836864 |
|---|---|
| author | Shi, Lingjuan Li, Wei Deng, Kai |
| author_facet | Shi, Lingjuan Li, Wei Deng, Kai |
| contents | 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)\geq\lceil\frac{n}{2}\rceil$, and the tree which obtained the lower bound is characterized. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_08557 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the maximal matchings of trees Shi, Lingjuan Li, Wei Deng, Kai Combinatorics 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)\geq\lceil\frac{n}{2}\rceil$, and the tree which obtained the lower bound is characterized. |
| title | On the maximal matchings of trees |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2506.08557 |