Convex universal fixers
Magdalena Lemańska ; Rita Zuazua
Discussiones Mathematicae Graph Theory, Tome 32 (2012), p. 807-812 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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 K̅ₙ. 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.

Publié le : 2012-01-01
EUDML-ID : urn:eudml:doc:271021 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1631,
     author = {Magdalena Lema\'nska and Rita Zuazua},
     title = {Convex universal fixers},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {32},
     year = {2012},
     pages = {807-812},
     zbl = {1297.05182},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1631}
}

Magdalena Lemańska; Rita Zuazua. Convex universal fixers. Discussiones Mathematicae Graph Theory, Tome 32 (2012) pp. 807-812. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1631/

[000] [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. | Zbl 1064.05111

[001] [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. | Zbl 1216.05098

[002] [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. | Zbl 1219.05116

[003] [4] R.G. Gibson, Bipartite graphs are not universal fixers, Discrete Math. 308 (2008) 5937-5943, doi: 10.1016/j.disc.2007.11.006. | Zbl 1181.05068

[004] [5] M. Lemańska, Weakly convex and convex domination numbers, Opuscula Math. 24 (2004) 181-188. | Zbl 1076.05060

[005] [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. | Zbl 1140.05302

[006] [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. | Zbl 1208.05102

[007] [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).

[008] [9] C.M. Mynhardt and Z. Xu, Domination in Prisms of Graphs: Universal Fixers, Util. Math. 78 (2009) 185-201. | Zbl 1284.05199

[009] [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. | Zbl 1238.05201