Global Domination and Packing Numbers

Abstract

For a graph $G=(V,E)$, $X\subseteq V$ is a global dominating set if $X$ dominates both $G$ and the complement graph $\overline{G}$. A set $X\subseteq 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 $\rho (G)$. We establish relationships between these and other graphical invariants, and characterize graphs for which $\rho (G)=\rho (\overline{G})$. Except for the two self-complementary graphs on $5$ vertices and when $G$ or $\overline{G}$ has isolated vertices, we show ${\gamma }_g(G)\le \lfloor n/2\rfloor$, where $n=|V|$.