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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1600,
author = {Linda Eroh and Ralucca Gera and Cong X. Kang and Craig E. Larson and Eunjeong Yi},
title = {Domination in functigraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {32},
year = {2012},
pages = {299-319},
zbl = {1255.05135},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1600}
}
Linda Eroh; Ralucca Gera; Cong X. Kang; Craig E. Larson; Eunjeong Yi. Domination in functigraphs. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 299-319. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1600/
[000] [1] S. Benecke, Domination of generalized Cartesian products, Ph.D. Dissertation (University of Victoria, 2009). | Zbl 1201.05069
[001] [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. | Zbl 1201.05069
[002] [3] C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam,1973).
[003] [4] C. Berge, Theory of Graphs and its Applications (Methuen, London, 1962).
[004] [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. | Zbl 1216.05098
[005] [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. | Zbl 1064.05111
[006] [7] G. Chartrand and F. Harary, Planar permutation graphs, Ann. Inst. H. Poincare (Sect. B) 3 (1967) 433-438. | Zbl 0162.27605
[007] [8] G. Chartrand and P. Zhang, Introduction to Graph Theory (McGraw-Hill, Kalamazoo, MI, 2004). | Zbl 1096.05001
[008] [9] A. Chen, D. Ferrero, R. Gera and E. Yi, Functigraphs: An Extension of Permutation Graphs, Math. Bohem. 136 (2011) 27-37. | Zbl 1224.05165
[009] [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. | Zbl 0384.05051
[010] [11] W. Dörfler, On mapping graphs and permutation graphs, Math. Slovaca 28 (1978) 277-288. | Zbl 0421.05035
[011] [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. | Zbl 1063.05107
[012] [13] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). | Zbl 0883.00011
[013] [14] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). | Zbl 0890.05002
[014] [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.
[015] [16] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ., 38, Providence, 1962). | Zbl 0105.35401