Partitioning a graph into alliance free sets

    Authors

    K. Shafique;R. D. Dutton

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    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

    WOS:000266654300017

    ISSN

    0012-365X

    Share

    COinS