| Title: | Partial domination in supercubic graphs |
|---|
| Authors: | ID Bujtás, Csilla (Author)
ID Henning, Michael A. (Author)
ID Klavžar, Sandi (Author) |
|---|
| Files: |  URL - Source URL, visit https://www.sciencedirect.com/science/article/pii/S0012365X23003552
 PDF - Presentation file, download (304,87 KB)
MD5: ACE2EBE8F78937B8559A1EBDBF9D5E0F
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| Abstract: | For some $\alpha$ with $0 < \alpha \le 1$, a subset $X$ of vertices in a graph $G$ of order $n$ is an $\alpha$-partial dominating set of $G$ if the set $X$ dominates at least $\alpha \times n$ vertices in $G$. The $\alpha$-partial domination number ${\rm pd}_{\alpha}(G)$ of $G$ is the minimum cardinality of an $\alpha$-partial dominating set of $G$. In this paper partial domination of graphs with minimum degree at least $3$ is studied. It is proved that if $G$ is a graph of order $n$ and with $\delta(G)\ge 3$, then ${\rm pd}_{\frac{7}{8}}(G) \le \frac{1}{3}n$. If in addition $n\ge 60$, then ${\rm pd}_{\frac{9}{10}}(G) \le \frac{1}{3}n$, and if $G$ is a connected cubic graph of order $n\ge 28$, then ${\rm pd}_{\frac{13}{14}}(G) \le \frac{1}{3}n$. Along the way it is shown that there are exactly four connected cubic graphs of order $14$ with domination number $5$. |
|---|
| Keywords: | domination, partial domination, cubic graphs, supercubic graphs |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.01.2024 |
|---|
| Year of publishing: | 2024 |
|---|
| Number of pages: | 11 str. |
|---|
| Numbering: | Vol. 347, iss. 1, article no. 113669 |
|---|
| PID: | 20.500.12556/DiRROS-18189  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 0012-365X |
|---|
| DOI: | 10.1016/j.disc.2023.113669 |
|---|
| COBISS.SI-ID: | 162890243 |
|---|
| Publication date in DiRROS: | 15.02.2024 |
|---|
| Views: | 1036 |
|---|
| Downloads: | 563 |
|---|
| 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. |
