We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A lower bound on the global powerful alliance number in trees.
- Authors
Ouatiki, Saliha; Bouzefrane, Mohamed
- Abstract
For a graph G = (V, E), a set D ⊆ V is a dominating set if every vertex in V − D is either in D or has a neighbor in D. A dominating set D is a global offensive alliance (resp. a global defensive alliance) if for each vertex v in V − D (resp. v in D) at least half the vertices from the closed neighborhood of v are in D. A global powerful alliance is both global defensive and global offensive. The global powerful alliance number γpa(G) is the minimum cardinality of a global powerful alliance of G. We show that if T is a tree of order n with l leaves and s support vertices, then γpa(T) ≥ 3n-2l-s+2/5 γ pa (T) ≥ 3 n - 2 l - s + 2 5 $ {\gamma }_{{pa}}(T)\enspace \ge \enspace \frac{3n-2l-s+2\enspace }{5}$. Moreover, we provide a constructive characterization of all extremal trees attaining this bound.
- Subjects
MATHEMATICAL bounds; GRAPH theory; GEOMETRIC vertices; SET theory; CARDINAL numbers
- Publication
RAIRO: Operations Research (2804-7303), 2021, Vol 55, Issue 2, p495
- ISSN
2804-7303
- Publication type
Article
- DOI
10.1051/ro/2021028