- Tytuł:
- A Classification of Cactus Graphs According to their Domination Number
- Autorzy:
-
Hajian, Majid
Henning, Michael A.
Rad, Nader Jafari - Powiązania:
- https://bibliotekanauki.pl/articles/32315639.pdf
- Data publikacji:
- 2022-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
domination number
lower bounds
cycles
cactus graphs - Opis:
- A set S of vertices in a graph G is a dominating set of G if every vertex not in S is adjacent to some vertex in S. The domination number, γ(G), of G is the minimum cardinality of a dominating set of G. The authors proved in [A new lower bound on the domination number of a graph, J. Comb. Optim. 38 (2019) 721–738] that if G is a connected graph of order n ≥ 2 with k ≥ 0 cycles and ℓ leaves, then γ(G) ≥ ⌈(n − ℓ + 2 − 2k)/3⌉. As a consequence of the above bound, γ(G) = (n − ℓ + 2(1 − k) + m)/3 for some integer m ≥ 0. In this paper, we characterize the class of cactus graphs achieving equality here, thereby providing a classification of all cactus graphs according to their domination number.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2022, 42, 2; 613-626
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł