Partitioning a graph into alliance free sets |
| |
Authors: | Khurram Shafique Ronald D Dutton |
| |
Institution: | School of Computer Science, University of Central Florida, Orlando, FL 32816, USA |
| |
Abstract: | A strong defensive alliance in a graph G=(V,E) is a set of vertices A⊆V, for which every vertex v∈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. |
| |
Keywords: | Alliance Defensive alliance Alliance-free set Alliance cover set Vertex partition |
本文献已被 ScienceDirect 等数据库收录! |
|