Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420574 | Discrete Applied Mathematics | 2009 | 8 Pages |
Abstract
A defensive alliance in a graph G=(V,E)G=(V,E) is a set of vertices S⊆VS⊆V satisfying the condition that, for each v∈Sv∈S, at least one half of its closed neighbors are in SS. A defensive alliance SS is called a critical defensive alliance if any vertex is removed from SS, then the resulting vertex set is not a defensive alliance any more. An alliance SS is called global if every vertex in V(G)∖SV(G)∖S is adjacent to at least one member of the alliance SS. In this paper, we shall propose a way for finding a critical global defensive alliance of star graphs. After counting the number of vertices in the critical global defensive alliance, we can derive an upper bound to the size of the minimum global defensive alliances in star graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Cheng-Ju Hsu, Fu-Hsing Wang, Yue-Li Wang,