PDF
Discussiones Mathematicae Graph Theory 32(4) (2012)
807-812
DOI: https://doi.org/10.7151/dmgt.1631
Convex Universal Fixers
| Magdalena Lemańska
Gdańsk University of Technology | Rita Zuazua
Departamento de Matematicas, Facultad de Ciencias |
Abstract
In [1] Burger and Mynhardt introduced the idea of universal fixers. Let G = (V, E) be a graph with n vertices and G ′ a copy of G. For a bijective function π: V(G) → V(G ′), define the prism πG of G as follows: V( πG) = V(G) ∪V(G ′) and E( πG) = E(G) ∪E(G ′) ∪M π, where M π = {u π(u) | u ∈ V(G)}. Let γ(G) be the domination number of G. If γ( πG) = γ(G) for any bijective function π, then G is called a universal fixer. In [9] it is conjectured that the only universal fixers are the edgeless graphs [ #xffe3;(Kn)].In this work we generalize the concept of universal fixers to the convex universal fixers. In the second section we give a characterization for convex universal fixers (Theorem 6) and finally, we give an in infinite family of convex universal fixers for an arbitrary natural number n ≥ 10.
Keywords: convex sets, dominating sets, universal fixers
2010 Mathematics Subject Classification: 05C69, 05C99.
References
| [1] | 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. |
| [2] | 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. |
| [3] | E.J. Cockayne, R.G. Gibson and C.M. Mynhardt, Claw-free graphs are not universal fixers, Discrete Math. 309 (2009) 128--133, doi: 10.1016/j.disc.2007.12.053. |
| [4] | R.G. Gibson, Bipartite graphs are not universal fixers, Discrete Math. 308 (2008) 5937--5943, doi: 10.1016/j.disc.2007.11.006. |
| [5] | M. Lemańska, Weakly convex and convex domination numbers, Opuscula Math. 24 (2004) 181--188. |
| [6] | J. Cyman, M. Lemańska and J. Raczek, Graphs with convex domination number close to their order, Discuss. Math. Graph Theory 26 (2006) 307--316, doi: 10.7151/dmgt.1322. |
| [7] | J. Raczek and M. Lemańska, A note of the weakly convex and convex domination numbers of a torus, Discrete Appl. Math. 158 (2010) 1708--1713, doi: 10.1016/j.dam.2010.06.001. |
| [8] | M. Lemańska, I. González Yero and J.A. Rodríguez-Velázquez, Nordhaus-Gaddum results for a convex domination number of a graph, Acta Math. Hungar., to appear (2011). |
| [9] | C.M. Mynhardt and Z. Xu, Domination in Prisms of Graphs: Universal Fixers, Util. Math. 78 (2009) 185--201. |
| [10] | C.M. Mynhardt and M. Schurch, Paired domination in prisms of graphs, Discuss. Math. Graph Theory 31 (2011) 5--23, doi: 10.7151/dmgt.1526. |
Received 25 August 2011
Revised 14 November 2011
Accepted 18 November 2011
Close