Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Opuscula Mathematica

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

A note on global alliances in trees

Bouzefrane M., Chellali M.

Opuscula Mathematica

2011

Vol. 31, no. 2

153-159

For a graph G = (V,E), a set S ⊆ V is a dominating set if every vertex in V - S has at least a neighbor in S. A dominating set S is a global offensive (respectively, defensive) alliance if for each vertex in V - S (respectively, in S) at least half the vertices from the closed neighborhood of v are in S. The domination number γ (G) is the minimum cardinality of a dominating set of G, and the global offensive alliance number γo(G) (respectively, global defensive alliance number γa(G)) is the minimum cardinality of a global offensive alliance (respectively, global deffensive alliance) of G. We show that if T is a tree of order n, then γo(T) ≤ 2γ (T) - 1 and if n ≥ 3, then γo(T) ≤ 3/2?a(T) ? 1. Moreover, all extremal trees attaining the first bound are characterized.

On the global offensive alliance number of a tree

Bouzefrane M., Chellali M.

Opuscula Mathematica

2009

Vol. 29, no. 3

223-228

For a graph G = (V, E), a set S ⊆ V is a dominating set if every vertex in V - S has at least a neighbor in S. A dominating set S is a global offensive alliance if for every vertex v in V - S, at least half of the vertices in its closed neighborhood are in S. The domination number ϒ(G) is the minimum cardinality of a dominating set of G and the global offensive alliance number ϒo(G) is the minimum cardinality of a global offensive alliance of G. We first show that every tree of order at least three with l leaves and s support vertices satisfies ϒo(T) ≥ (n - l + s + 1)/3 and we characterize extremal trees attaining this lower bound. Then we give a constructive characterization of trees with equal domination and global offensive alliance numbers.