Domination in functigraphs

DOI10.7151/DMGT.1600zbMATH Open1255.05135arXiv1106.1147OpenAlexW2016039405MaRDI QIDQ4647871FDOQ4647871

Authors: Linda Eroh, Ralucca Gera, Cong X. Kang, Craig E. Larson, Eunjeong Yi

Publication date: 8 November 2012

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Abstract: Let

G_{1}

and

G_{2}

be disjoint copies of a graph

G

, and let

f : V (G_{1}) i g h t a r r o w V (G_{2})

be a function. Then a emph{functigraph}

C (G, f) = (V, E)

has the vertex set

V = V (G_{1}) c u p V (G_{2})

and the edge set

E = E (G_{1}) c u p E (G_{2}) c u p u v m i d u i n V (G_{1}), v i n 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 a m m a (G)

denote the domination number of

G

. It is readily seen that

g a m m a (G) l e g a m m a (C (G, f)) l e 2 g a m m a (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.

Full work available at URL: https://arxiv.org/abs/1106.1147

Recommendations

zbMATH Keywords

domination permutation graphs generalized prisms functigraphs

Mathematics Subject Classification ID

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

Cited In (10)

This page was built for publication: Domination in functigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4647871)