On the equality of domination number and 2-domination number

Gülnaz, Boruzanli Ekinci (avtor), Bujtás, Csilla (avtor)

The $2$-domination number $\gamma_2(G)$ of a graph $G$ is the minimum cardinality of a set $D \subseteq V(G)$ for which every vertex outside $D$ is adjacent to at least two vertices in ▫$D$▫. Clearly, $\gamma_2(G)$ cannot be smaller than the domination number $\gamma(G)$. We consider a large class of graphs and characterize those members which satisfy $\gamma_2=\gamma$. For the general case, we prove that it is NP-hard to decide whether $\gamma_2=\gamma$ holds. We also give a necessary and sufficient condition for a graph to satisfy the equality hereditarily.

• Jezik: Angleški jezik
• Ključne besede: domination number, 2-domination number, hereditary property, computational complexity
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Datum objave: 01.01.2024
• Leto izida: 2024
• Št. strani: Str. 383-406
• Številčenje: Vol. 44, no. 1
• PID: 20.500.12556/RUL-163136
• UDK: 519.17
• ISSN pri članku: 1234-3099
• DOI: 10.7151/dmgt.2452
• COBISS.SI-ID: 117087491
• Datum objave v RUL: 02.10.2024

Gradivo je del revije

• Naslov: Discussiones mathematicae. Graph theory
• Skrajšan naslov: Discuss. Math., Graph Theory
• Založnik: Technical University Press
• ISSN: 1234-3099
• COBISS.SI-ID: 7487065

Licence

• Licenca: CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
• Opis: Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.

Projekti

• Financer: ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
• Številka projekta: N1-0108
• Naslov: Prenos naboja v grafovski dominaciji