Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: locating-total domination

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

On locating and differentiating-total domination in trees

100%

Chellali M.

Discussiones Mathematicae Graph Theory

2008

tom 28

nr 3

383-392

A total dominating set of a graph G = (V,E) with no isolated vertex is a set S ⊆ V such that every vertex is adjacent to a vertex in S. A total dominating set S of a graph G is a locating-total dominating set if for every pair of distinct vertices u and v in V-S, N(u)∩S ≠ N(v)∩S, and S is a differentiating-total dominating set if for every pair of distinct vertices u and v in V, N[u]∩S ≠ N[v] ∩S. Let $γₜ^L(G)$ and $γₜ^D(G)$ be the minimum cardinality of a locating-total dominating set and a differentiating-total dominating set of G, respectively. We show that for a nontrivial tree T of order n, with l leaves and s support vertices, $γₜ^L(T) ≥ max{2(n+l-s+1)/5,(n+2-s)/2}$, and for a tree of order n ≥ 3, $γₜ^D(T) ≥ 3(n+l-s+1)/7$, improving the lower bounds of Haynes, Henning and Howard. Moreover we characterize the trees satisfying $γₜ^L(T) = 2(n+l- s+1)/5$ or $γₜ^D(T) = 3(n+l-s+1)/7$.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Chellali M.

1 2008

Wyniki wyszukiwania

On locating and differentiating-total domination in trees