Title

Global Domination And Packing Numbers

Abstract

For a graph G = (V, E), X ⊆ V is a global dominating set if X dominates both G and the complement graph G. A set X ⊆ 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 γ8(G), and the maximum number in any packing is ρ(G). We establish relationships between these and other graphical invariants, and characterize graphs for which p(G) = ρ(G). Except for the two self-complementary graphs on 5 vertices and when G or ̄ has isolated vertices, we show γg(G) ≤⌊n/2⌋, where n = |V|.

Publication Date

7-1-2011

Publication Title

Ars Combinatoria

Volume

101

Number of Pages

489-501

Document Type

Article

Personal Identifier

scopus

Socpus ID

79959387561 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS