# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

# Discussiones Mathematicae Graph Theory

## 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

## Abstract

In  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  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

  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.  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.  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.  R.G. Gibson, Bipartite graphs are not universal fixers, Discrete Math. 308 (2008) 5937--5943, doi: 10.1016/j.disc.2007.11.006.  M. Lemańska, Weakly convex and convex domination numbers, Opuscula Math. 24 (2004) 181--188.  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.  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.  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).  C.M. Mynhardt and Z. Xu, Domination in Prisms of Graphs: Universal Fixers, Util. Math. 78 (2009) 185--201.  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.