| Title: | Best possible upper bounds on the restrained domination number of cubic graphs |
|---|
| Authors: | ID Brešar, Boštjan (Author)
ID Henning, Michael A. (Author) |
|---|
| Files: |  PDF - Presentation file, download (2,13 MB)
MD5: 5A65E5661DF4CBFCFB55FA237EAE42DB
 URL - Source URL, visit https://onlinelibrary.wiley.com/doi/10.1002/jgt.23095
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| Abstract: | 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 $\gamma(G)$ and the restrained domination number $\gamma_{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 $\gamma(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 $\gamma_{r}(G) \le \frac{2}{5}n$. |
|---|
| Keywords: | domination, restrained domination, cubic graphs |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.08.2024 |
|---|
| Year of publishing: | 2024 |
|---|
| Number of pages: | str. 763–815 |
|---|
| Numbering: | Vol. 106, iss. 4 |
|---|
| PID: | 20.500.12556/DiRROS-19113  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 0364-9024 |
|---|
| DOI: | 10.1002/jgt.23095 |
|---|
| COBISS.SI-ID: | 199137795 |
|---|
| Note: |
|
|---|
| Publication date in DiRROS: | 18.06.2024 |
|---|
| Views: | 140 |
|---|
| Downloads: | 129 |
|---|
| Metadata: |     |
|---|
|
:
|
Copy citation |
|---|
| | | | Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
