- Tytuł:
- Algorithmic aspects of total-subdomination in graphs
- Autorzy:
-
Harris, Laura
Hattingh, Johannes
Henning, Michael - Powiązania:
- https://bibliotekanauki.pl/articles/744186.pdf
- Data publikacji:
- 2006
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
total k-subdomination
algorithm
tree - Opis:
- Let G = (V,E) be a graph and let k ∈ Z⁺. A total k-subdominating function is a function f: V → {-1,1} such that for at least k vertices v of G, the sum of the function values of f in the open neighborhood of v is positive. The total k-subdomination number of G is the minimum value of f(V) over all total k-subdominating functions f of G where f(V) denotes the sum of the function values assigned to the vertices under f. In this paper, we present a cubic time algorithm to compute the total k-subdomination number of a tree and also show that the associated decision problem is NP-complete for general graphs.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2006, 26, 1; 5-18
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł