- Tytuł:
- On equality in an upper bound for the acyclic domination number
- Autorzy:
- Samodivkin, V.
- Powiązania:
- https://bibliotekanauki.pl/articles/255046.pdf
- Data publikacji:
- 2008
- Wydawca:
- Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
- Tematy:
-
dominating set
acyclic set
independent set
acyclic domination number - Opis:
- A subset A of vertices in a graph G is acyclic if the subgraph it induces contains no cycles. The acyclic domination number ϒa (G) of a graph G is the minimum cardinality of an acyclic dominating set of G. For any graph G with n vertices and maximum degree Δ(G), ϒa(G) ≤ n - Δ(G). In this paper we characterize the connected graphs and the connected triangle-free graphs which achieve this upper bound.
- Źródło:
-
Opuscula Mathematica; 2008, 28, 3; 331-334
1232-9274
2300-6919 - Pojawia się w:
- Opuscula Mathematica
- Dostawca treści:
- Biblioteka Nauki
Artykuł