Domination in Functigraphs

Linda Eroh; Ralucca Gera; Cong X. Kang; Craig E. Larson; Eunjeong Yi

paper

Domination in Functigraphs

arXiv:1106.1147

Abstract

Let $G_{1}$ and $G_{2}$ be disjoint copies of a graph $G$ , and let $f : V (G_{1}) \to V (G_{2})$ be a function. Then a \emph{functigraph} $C (G, f) = (V, E)$ has the vertex set $V = V (G_{1}) \cup V (G_{2})$ and the edge set $E = E (G_{1}) \cup E (G_{2}) \cup {uv ∣ u \in V (G_{1}), v \in V (G_{2}), v = f (u)}$ . A functigraph is a generalization of a \emph{permutation graph} (also known as a \emph{generalized prism}) in the sense of Chartrand and Harary. In this paper, we study domination in functigraphs. Let $γ (G)$ denote the domination number of $G$ . It is readily seen that $γ (G) \leq γ (C (G, f)) \leq 2 γ (G)$ . We investigate for graphs generally, and for cycles in great detail, the functions which achieve the upper and lower bounds, as well as the realization of the intermediate values.

18 pages, 8 figures