Best possible upper bounds on the restrained domination number of cubic graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913283185836032 |
|---|---|
| author | Brešar, Boštjan Henning, Michael A. |
| author_facet | Brešar, Boštjan Henning, Michael A. |
| contents | A dominating set in a graph $G$ is a set $S$ of vertices such that every vertex in $V(G) \setminus S$ is adjacent to a vertex in $S$. A restrained dominating set of $G$ is a dominating set $S$ with the additional restraint that the graph $G - S$ obtained by removing all vertices in $S$ is isolate-free. The domination number $γ(G)$ and the restrained domination number $γ_{r}(G)$ are the minimum cardinalities of a dominating set and restrained dominating set, respectively, of $G$. Let $G$ be a cubic graph of order~$n$. A classical result of Reed [Combin. Probab. Comput. 5 (1996), 277--295] states that $γ(G) \le \frac{3}{8}n$, and this bound is best possible. To determine a best possible upper bound on the restrained domination number of $G$ is more challenging, and we prove that $γ_{r}(G) \le \frac{2}{5}n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_17129 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Best possible upper bounds on the restrained domination number of cubic graphs Brešar, Boštjan Henning, Michael A. Combinatorics 05C69 A dominating set in a graph $G$ is a set $S$ of vertices such that every vertex in $V(G) \setminus S$ is adjacent to a vertex in $S$. A restrained dominating set of $G$ is a dominating set $S$ with the additional restraint that the graph $G - S$ obtained by removing all vertices in $S$ is isolate-free. The domination number $γ(G)$ and the restrained domination number $γ_{r}(G)$ are the minimum cardinalities of a dominating set and restrained dominating set, respectively, of $G$. Let $G$ be a cubic graph of order~$n$. A classical result of Reed [Combin. Probab. Comput. 5 (1996), 277--295] states that $γ(G) \le \frac{3}{8}n$, and this bound is best possible. To determine a best possible upper bound on the restrained domination number of $G$ is more challenging, and we prove that $γ_{r}(G) \le \frac{2}{5}n$. |
| title | Best possible upper bounds on the restrained domination number of cubic graphs |
| topic | Combinatorics 05C69 |
| url | https://arxiv.org/abs/2403.17129 |