| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4649819 | Discrete Mathematics | 2009 | 4 Pages |
Abstract
A strong defensive alliance in a graph G=(V,E)G=(V,E) is a set of vertices A⊆VA⊆V, for which every vertex v∈Av∈A has at least as many neighbors in AA as in V−AV−A. We call a partition A,BA,B of vertices to be an alliance-free partition, if neither AA nor BB contains a strong defensive alliance as a subset. We prove that a connected graph GG has an alliance-free partition exactly when GG has a block that is other than an odd clique or an odd cycle.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Khurram Shafique, Ronald D. Dutton,