- Tytuł:
- A note on bipartite graphs whose [1, k]-domination number equal to their number of vertices
- Autorzy:
-
Ghareghani, Narges
Peterin, Iztok
Sharifani, Pouyeh - Powiązania:
- https://bibliotekanauki.pl/articles/256007.pdf
- Data publikacji:
- 2020
- Wydawca:
- Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
- Tematy:
-
domination
[1, k]-domination number
[l,k]-total domination number
bipartite graphs - Opis:
- A subset D of the vertex set V of a graph G is called an [1, k]-dominating set if every vertex from V — D is adjacent to at least one vertex and at most fc vertices of D. A [1, k]-dominating set with the minimum number of vertices is called a [formula]-set and the number of its vertices is the [1, k]-domination number [formula] of G. In this short note we show that the decision problem whether [formula] is an NP-hard problem, even for bipartite graphs. Also, a simple construction of a bipartite graph G of order n satisfying [formula] is given for every integer n ≥ (k + l)(2k + 3).
- Źródło:
-
Opuscula Mathematica; 2020, 40, 3; 375-382
1232-9274
2300-6919 - Pojawia się w:
- Opuscula Mathematica
- Dostawca treści:
- Biblioteka Nauki
Artykuł