- Tytuł:
- On Independent [1, 2]-Sets in Trees
- Autorzy:
-
Aleid, Sahar A.
Cáceres, José
Puertas, María Luz - Powiązania:
- https://bibliotekanauki.pl/articles/31342284.pdf
- Data publikacji:
- 2018-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
domination
independence
spanning trees
excellent trees - Opis:
- An [1, k]-set S in a graph G is a dominating set such that every vertex not in S has at most k neighbors in it. If the additional requirement that the set must be independent is added, the existence of such sets is not guaranteed in every graph. In this paper we solve some problems previously posed by other authors about independent [1, 2]-sets. We provide a necessary condition for a graph to have an independent [1, 2]-set, in terms of spanning trees, and we prove that this condition is also sufficient for cactus graphs. We follow the concept of excellent tree and characterize the family of trees such that any vertex belongs to some independent [1, 2]-set. Finally, we describe a linear algorithm to decide whether a tree has an independent [1, 2]-set. This algorithm can be easily modified to obtain the cardinality of a smallest independent [1, 2]-set of a tree.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2018, 38, 3; 645-660
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł