# Domination in functigraphs

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

Discussiones Mathematicae Graph Theory (2012)

- Volume: 32, Issue: 2, page 299-319
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topLinda Eroh, et al. "Domination in functigraphs." Discussiones Mathematicae Graph Theory 32.2 (2012): 299-319. <http://eudml.org/doc/270825>.

@article{LindaEroh2012,

abstract = {Let G₁ and G₂ be disjoint copies of a graph G, and let f:V(G₁) → V(G₂) be a function. Then a functigraph C(G,f) = (V,E) has the vertex set V = V(G₁) ∪ V(G₂) and the edge set E = E(G₁) ∪ E(G₂) ∪ \{uv | u ∈ V(G₁), v ∈ V(G₂),v = f(u)\}. A functigraph is a generalization of a permutation graph (also known as a 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) ≤ γ(C(G,f)) ≤ 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.},

author = {Linda Eroh, Ralucca Gera, Cong X. Kang, Craig E. Larson, Eunjeong Yi},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {domination; permutation graphs; generalized prisms; functigraphs},

language = {eng},

number = {2},

pages = {299-319},

title = {Domination in functigraphs},

url = {http://eudml.org/doc/270825},

volume = {32},

year = {2012},

}

TY - JOUR

AU - Linda Eroh

AU - Ralucca Gera

AU - Cong X. Kang

AU - Craig E. Larson

AU - Eunjeong Yi

TI - Domination in functigraphs

JO - Discussiones Mathematicae Graph Theory

PY - 2012

VL - 32

IS - 2

SP - 299

EP - 319

AB - Let G₁ and G₂ be disjoint copies of a graph G, and let f:V(G₁) → V(G₂) be a function. Then a functigraph C(G,f) = (V,E) has the vertex set V = V(G₁) ∪ V(G₂) and the edge set E = E(G₁) ∪ E(G₂) ∪ {uv | u ∈ V(G₁), v ∈ V(G₂),v = f(u)}. A functigraph is a generalization of a permutation graph (also known as a 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) ≤ γ(C(G,f)) ≤ 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.

LA - eng

KW - domination; permutation graphs; generalized prisms; functigraphs

UR - http://eudml.org/doc/270825

ER -

## References

top- [1] S. Benecke, Domination of generalized Cartesian products, Ph.D. Dissertation (University of Victoria, 2009). Zbl1201.05069
- [2] S. Benecke and C.M. Mynhardt, Domination of generalized Cartesian products, Discrete Math. 310 (2010) 1392-1397, doi: 10.1016/j.disc.2009.12.007. Zbl1201.05069
- [3] C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam,1973).
- [4] C. Berge, Theory of Graphs and its Applications (Methuen, London, 1962).
- [5] A.P. Burger and C.M. Mynhardt, Regular graphs are not universal fixers, Discrete Math. 310 (2010) 364-368, doi: 10.1016/j.disc.2008.09.016. Zbl1216.05098
- [6] A.P. Burger, C.M. Mynhardt and W.D. Weakley, On the domination number of prisms of graphs, Discuss. Math. Graph Theory 24 (2004) 303-318, doi: 10.7151/dmgt.1233. Zbl1064.05111
- [7] G. Chartrand and F. Harary, Planar permutation graphs, Ann. Inst. H. Poincare (Sect. B) 3 (1967) 433-438. Zbl0162.27605
- [8] G. Chartrand and P. Zhang, Introduction to Graph Theory (McGraw-Hill, Kalamazoo, MI, 2004). Zbl1096.05001
- [9] A. Chen, D. Ferrero, R. Gera and E. Yi, Functigraphs: An Extension of Permutation Graphs, Math. Bohem. 136 (2011) 27-37. Zbl1224.05165
- [10] E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977) 247-261, doi: 10.1002/net.3230070305. Zbl0384.05051
- [11] W. Dörfler, On mapping graphs and permutation graphs, Math. Slovaca 28 (1978) 277-288. Zbl0421.05035
- [12] B.L. Hartnell and D.F. Rall, On dominating the cartesian product of a graph and K₂, Discuss. Math. Graph Theory 24 (2004) 389-402, doi: 10.7151/dmgt.1238. Zbl1063.05107
- [13] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). Zbl0883.00011
- [14] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
- [15] S.T. Hedetniemi, On classes of graphs defined by special cutsets of lines, Many Facets of Graph Theory, Lect. Notes Math. 110 (1969) 171-189, doi: 10.1007/BFb0060115.
- [16] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ., 38, Providence, 1962). Zbl0105.35401

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.