Title

Partitioning A Graph Into Alliance Free Sets

Keywords

Alliance; Alliance cover set; Alliance-free set; Defensive alliance; Vertex partition

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. © 2008 Elsevier B.V. All rights reserved.

Publication Date

5-28-2009

Publication Title

Discrete Mathematics

Volume

309

Issue

10

Number of Pages

3102-3105

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.disc.2008.08.011

Socpus ID

67349103362 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/67349103362

This document is currently not available here.

Share

COinS