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

Abstract

top
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.

How to cite

top

Linda 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. [1] S. Benecke, Domination of generalized Cartesian products, Ph.D. Dissertation (University of Victoria, 2009). Zbl1201.05069
  2. [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. [3] C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam,1973). 
  4. [4] C. Berge, Theory of Graphs and its Applications (Methuen, London, 1962). 
  5. [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. [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. [7] G. Chartrand and F. Harary, Planar permutation graphs, Ann. Inst. H. Poincare (Sect. B) 3 (1967) 433-438. Zbl0162.27605
  8. [8] G. Chartrand and P. Zhang, Introduction to Graph Theory (McGraw-Hill, Kalamazoo, MI, 2004). Zbl1096.05001
  9. [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. [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. [11] W. Dörfler, On mapping graphs and permutation graphs, Math. Slovaca 28 (1978) 277-288. Zbl0421.05035
  12. [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. [13] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). Zbl0883.00011
  14. [14] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  15. [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. [16] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ., 38, Providence, 1962). Zbl0105.35401

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.