| Title: | Computational complexity aspects of super domination |
|---|
| Authors: | ID Bujtás, Csilla (Author)
ID Ghanbari, Nima (Author)
ID Klavžar, Sandi (Author) |
|---|
| Files: |  URL - Source URL, visit https://www.sciencedirect.com/science/article/pii/S0304397523004504
 PDF - Presentation file, download (453,39 KB)
MD5: E30A15BCE1A2914775BF45D96D19B10F
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| Abstract: | Let ▫$G$▫ be a graph. A dominating set ▫$D\subseteq V(G)$▫ is a super dominating set if for every vertex ▫$x\in V(G) \setminus D$▫ there exists ▫$y\in D$▫ such that ▫$N_G(y)\cap (V(G)\setminus D)) = \{x\}$▫. The cardinality of a smallest super dominating set of ▫$G$▫ is the super domination number of ▫$G$▫. An exact formula for the super domination number of a tree ▫$T$▫ is obtained, and it is demonstrated that a smallest super dominating set of ▫$T$▫ can be computed in linear time. It is proved that it is NP-complete to decide whether the super domination number of a graph ▫$G$▫ is at most a given integer if ▫$G$▫ is a bipartite graph of girth at least ▫$8$▫. The super domination number is determined for all ▫$k$▫-subdivisions of graphs. Interestingly, in half of the cases the exact value can be efficiently computed from the obtained formulas, while in the other cases the computation is hard. While obtaining these formulas, II-matching numbers are introduced and proved that they are computationally hard to determine. |
|---|
| Keywords: | super domination number, trees, bipartite graphs, k-subdivision of a graph, computational complexity, matching, II-matching number |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.10.2023 |
|---|
| Year of publishing: | 2023 |
|---|
| Number of pages: | 14 str. |
|---|
| Numbering: | Vol. 975, art. no. 114137 |
|---|
| PID: | 20.500.12556/DiRROS-18405  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 0304-3975 |
|---|
| DOI: | 10.1016/j.tcs.2023.114137 |
|---|
| COBISS.SI-ID: | 162318851 |
|---|
| Note: |
|
|---|
| Publication date in DiRROS: | 14.03.2024 |
|---|
| Views: | 518 |
|---|
| Downloads: | 206 |
|---|
| 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. |
