Paired domination in trees: A linear algorithm and asymptotic normality
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_ | 1866912389562105856 |
|---|---|
| author | Henning, Michael A. Ralaivaosaona, Dimbinaina |
| author_facet | Henning, Michael A. Ralaivaosaona, Dimbinaina |
| contents | A set $S$ of vertices in a graph $G$ is a paired dominating set if every vertex of $G$ is adjacent to a vertex in $S$ and the subgraph induced by $S$ contains a perfect matching (not necessarily as an induced subgraph). The paired domination number, $γ_{\mathrm{pr}}(G)$, of $G$ is the minimum cardinality of a paired dominating set of $G$. We present a linear algorithm for computing the paired domination number of a tree. As an application of our algorithm, we prove that the paired domination number is asymptotically normal in a random rooted tree of order $n$ generated by a conditioned Galton-Watson process as $n\to\infty$. In particular, we have found that the paired domination number of a random Cayley tree of order $n$, where each tree is equally likely, is asymptotically normal with expectation approaching $(0.5177\ldots)n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_17672 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Paired domination in trees: A linear algorithm and asymptotic normality Henning, Michael A. Ralaivaosaona, Dimbinaina Combinatorics 05C69, 60C05 A set $S$ of vertices in a graph $G$ is a paired dominating set if every vertex of $G$ is adjacent to a vertex in $S$ and the subgraph induced by $S$ contains a perfect matching (not necessarily as an induced subgraph). The paired domination number, $γ_{\mathrm{pr}}(G)$, of $G$ is the minimum cardinality of a paired dominating set of $G$. We present a linear algorithm for computing the paired domination number of a tree. As an application of our algorithm, we prove that the paired domination number is asymptotically normal in a random rooted tree of order $n$ generated by a conditioned Galton-Watson process as $n\to\infty$. In particular, we have found that the paired domination number of a random Cayley tree of order $n$, where each tree is equally likely, is asymptotically normal with expectation approaching $(0.5177\ldots)n$. |
| title | Paired domination in trees: A linear algorithm and asymptotic normality |
| topic | Combinatorics 05C69, 60C05 |
| url | https://arxiv.org/abs/2505.17672 |