An upper bound on the 2-outer-independent domination number of a tree

Marcin Krzywkowski

doi:10.1016/j.crma.2011.10.005

An upper bound on the 2-outer-independent domination number of a tree

Abstrakt

A 2-outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)D has a at least two neighbors in D, and the set V(G)D is independent. The 2-outer-independent domination number of a graph G, denoted by gamma_2^{oi}(G), is the minimum cardinality of a 2-outer-independent dominating set of G. We prove that for every nontrivial tree T of order n with l leaves we have gamma_2^{oi}(T) <= (n+l)/2, and we characterize the trees attaining this upper bound.

Cytowania

6

CrossRef
0

Web of Science
5

Scopus

Autor (1)

Marcin Krzywkowski dr inż.

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

DOMINATION

Informacje szczegółowe

Kategoria:: Publikacja w czasopiśmie
Typ:: artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:: COMPTES RENDUS MATHEMATIQUE nr 349, strony 1123 - 1125,
ISSN: 1631-073X
Język:: angielski
Rok wydania:: 2011
Opis bibliograficzny:: Krzywkowski M.: An upper bound on the 2-outer-independent domination number of a tree// COMPTES RENDUS MATHEMATIQUE. -Vol. 349, nr. Iss. 1 (2011), s.1123-1125
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.crma.2011.10.005
Weryfikacja:: Politechnika Gdańska