Global Domination and Packing Numbers

    Authors

    R. D. Dutton

    Comments

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

    Abbreviated Journal Title

    ARS Comb.

    Keywords

    GRAPHS; Mathematics

    Abstract

    For a graph G = (V, E), X subset of V is a global dominating set if X dominates both G and the complement graph (G) over bar. A set X C V is a packing if its pairwise members are distance at least 3 apart. The minimum number of vertices in any global dominating set is gamma(g)(G), and the maximum number in any packing is p(G). We establish relationships between these and other graphical invariants, and characterize graphs for which p(G) = p(G). Except for the two self complementary graphs on 5 vertices and when G or (G) over bar has isolated vertices, we show gamma(g)(G) < = left perpendicular n/2 right perpendicular, where n = vertical bar V vertical bar.

    Journal Title

    Ars Combinatoria

    Volume

    101

    Publication Date

    1-1-2011

    Document Type

    Article

    Language

    English

    First Page

    489

    Last Page

    501

    WOS Identifier

    WOS:000291893900040

    ISSN

    0381-7032

    Share

    COinS