Global defensive alliances in star graphs

Autor: Yue-Li Wang, Cheng-Ju Hsu, Fu-Hsing Wang
Rok vydání: 2009
Předmět:
Zdroj: Discrete Applied Mathematics. 157(8):1924-1931
ISSN: 0166-218X
DOI: 10.1016/j.dam.2009.01.005
Popis: A defensive alliance in a graph G=(V,E) is a set of vertices [email protected]?V satisfying the condition that, for each [email protected]?S, at least one half of its closed neighbors are in S. A defensive alliance S is called a critical defensive alliance if any vertex is removed from S, then the resulting vertex set is not a defensive alliance any more. An alliance S is called global if every vertex in V(G)@?S is adjacent to at least one member of the alliance S. 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.
Databáze: OpenAIRE