Paired domination in graphs with minimum degree four
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_ | 1866912360293203968 |
|---|---|
| author | Bujtás, Csilla Henning, Michael A. |
| author_facet | Bujtás, Csilla Henning, Michael A. |
| 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$ admits a perfect matching. The minimum cardinality of a paired dominating set of $G$ is the paired domination number $\gpr(G)$ of $G$. We show that if $G$ is a graph of order~$n$ and $δ(G) \ge 4$, then $\gpr(G) \le \frac{10}{17}n < 0.5883 n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_01815 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Paired domination in graphs with minimum degree four Bujtás, Csilla Henning, Michael A. Combinatorics 05C69 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$ admits a perfect matching. The minimum cardinality of a paired dominating set of $G$ is the paired domination number $\gpr(G)$ of $G$. We show that if $G$ is a graph of order~$n$ and $δ(G) \ge 4$, then $\gpr(G) \le \frac{10}{17}n < 0.5883 n$. |
| title | Paired domination in graphs with minimum degree four |
| topic | Combinatorics 05C69 |
| url | https://arxiv.org/abs/2505.01815 |