×

Domination in functigraphs. (English) Zbl 1255.05135

Summary: Let \(G_1\) and \(G_2\) be disjoint copies of a graph \(G\), and let \(f:V(G1) \to V(G_2)\) be a function. Then a 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 permutation graph (also known as a generalized prism) in the sense of G. Chartrand and F. Harary [Ann. Inst. Henri Poincaré, Nouv. Sér., Sect. B 3, 433–438 (1967; Zbl 0162.27605)].
In this paper, we study domination in functigraphs. Let \(\gamma (G)\) denote the domination number of \(G\). It is readily seen that \(\gamma (G) \leq \gamma (C(G,f)) \leq 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.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C38 Paths and cycles
05A05 Permutations, words, matrices

Citations:

Zbl 0162.27605
PDFBibTeX XMLCite
Full Text: DOI arXiv