Title
Partitioning a graph into alliance free sets
Abbreviated Journal Title
Discret. Math.
Keywords
Alliance; Defensive alliance; Alliance-free set; Alliance cover set; Vertex partition; DEGREE CONSTRAINTS; DECOMPOSING GRAPHS; MINIMUM DEGREE; CONNECTIVITY; Mathematics
Abstract
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.
Journal Title
Discrete Mathematics
Volume
309
Issue/Number
10
Publication Date
1-1-2009
Document Type
Article
Language
English
First Page
3102
Last Page
3105
WOS Identifier
ISSN
0012-365X
Recommended Citation
"Partitioning a graph into alliance free sets" (2009). Faculty Bibliography 2000s. 2118.
https://stars.library.ucf.edu/facultybib2000/2118
Comments
Authors: contact us about adding a copy of your work at STARS@ucf.edu