Domination in Functigraphs

Details Domination in Functigraphs Domination in Functigraphs

2011-06-06

arxiv.org/abs/1106.1147v1

Discuss. Math. Graph Theory, Vol. 32 (2012) pp. 299-319

Mathematics

Combinatorics

18 pages, 8 figures

Scientific paper

Let $G_1$ and $G_2$ be disjoint copies of a graph $G$, and let $f: V(G_1) \rightarrow 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 \mid 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 $\gamma(G)$ denote the domination number of $G$. It is readily seen that $\gamma(G) \le \gamma(C(G,f)) \le 2 \gamma(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.

Affiliated with

Also associated with

No associations

Rating

Domination in Functigraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Domination in Functigraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Domination in Functigraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-390663