| Naslov: | Computational complexity aspects of super domination |
|---|
| Avtorji: | ID Bujtás, Csilla (Avtor)
ID Ghanbari, Nima (Avtor)
ID Klavžar, Sandi (Avtor) |
|---|
| Datoteke: |  URL - Izvorni URL, za dostop obiščite https://www.sciencedirect.com/science/article/pii/S0304397523004504
 PDF - Predstavitvena datoteka, prenos (453,39 KB)
MD5: E30A15BCE1A2914775BF45D96D19B10F
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | 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. |
|---|
| Ključne besede: | super domination number, trees, bipartite graphs, k-subdivision of a graph, computational complexity, matching, II-matching number |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.10.2023 |
|---|
| Leto izida: | 2023 |
|---|
| Št. strani: | 14 str. |
|---|
| Številčenje: | Vol. 975, art. no. 114137 |
|---|
| PID: | 20.500.12556/DiRROS-18405  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 0304-3975 |
|---|
| DOI: | 10.1016/j.tcs.2023.114137 |
|---|
| COBISS.SI-ID: | 162318851 |
|---|
| Opomba: |
|
|---|
| Datum objave v DiRROS: | 14.03.2024 |
|---|
| Število ogledov: | 94 |
|---|
| Število prenosov: | 55 |
|---|
| Metapodatki: |     |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
