Partitioning a graph into alliance free sets
Abbreviated Journal Title
Alliance; Defensive alliance; Alliance-free set; Alliance cover set; Vertex partition; DEGREE CONSTRAINTS; DECOMPOSING GRAPHS; MINIMUM DEGREE; CONNECTIVITY; Mathematics
A strong defensive alliance in a graph G = (V, E) is a set of vertices A subset of V, for which every vertex v is an element of A has at least as many neighbors in A as in V - A. We call a partition A, B of vertices to be an alliance-free partition, if neither A nor B contains a strong defensive alliance as a Subset. We prove that a connected graph G has an alliance-free partition exactly when G has a block that is other than an odd clique or an odd cycle. (C) 2008 Elsevier B.V. All rights reserved.
"Partitioning a graph into alliance free sets" (2009). Faculty Bibliography 2000s. 2118.