Discussiones Mathematicae Graph Theory 32(4) (2012) 807-812
doi: 10.7151/dmgt.1631

[BIBTex] [PDF] [PS]

Convex Universal Fixers

Magdalena Lemańska

Gdańsk University of Technology
Narutowicza 11/12
80-233 Gdańsk, Poland

Rita Zuazua

Departamento de Matematicas, Facultad de Ciencias
UNAM, Mexico


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.


[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