Geodesic
Edgeless graphs are the only universal fixers
Czechoslovak Mathematical Journal, Tome 64 (2014) no. 3, pp. 833-843

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
Given two disjoint copies of a graph $G$, denoted $G^1$ and $G^2$, and a permutation $\pi $ of $V(G)$, the graph $\pi G$ is constructed by joining $u \in V(G^1)$ to $\pi (u) \in V(G^2)$ for all $u \in V(G^1)$. $G$ is said to be a universal fixer if the domination number of $\pi G$ is equal to the domination number of $G$ for all $\pi $ of $V(G)$. In 1999 it was conjectured that the only universal fixers are the edgeless graphs. Since then, a few partial results have been shown. In this paper, we prove the conjecture completely.
Given two disjoint copies of a graph $G$, denoted $G^1$ and $G^2$, and a permutation $\pi $ of $V(G)$, the graph $\pi G$ is constructed by joining $u \in V(G^1)$ to $\pi (u) \in V(G^2)$ for all $u \in V(G^1)$. $G$ is said to be a universal fixer if the domination number of $\pi G$ is equal to the domination number of $G$ for all $\pi $ of $V(G)$. In 1999 it was conjectured that the only universal fixers are the edgeless graphs. Since then, a few partial results have been shown. In this paper, we prove the conjecture completely.
DOI : 10.1007/s10587-014-0136-3
Classification : 05C69
Keywords: universal fixer; domination 
Wash, Kirsti. Edgeless graphs are the only universal fixers. Czechoslovak Mathematical Journal, Tome 64 (2014) no. 3, pp. 833-843. doi: 10.1007/s10587-014-0136-3
@article{10_1007_s10587_014_0136_3,
     author = {Wash, Kirsti},
     title = {Edgeless graphs are the only universal fixers},
     journal = {Czechoslovak Mathematical Journal},
     pages = {833--843},
     year = {2014},
     volume = {64},
     number = {3},
     doi = {10.1007/s10587-014-0136-3},
     mrnumber = {3298564},
     zbl = {06391529},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0136-3/}
}
TY  - JOUR
AU  - Wash, Kirsti
TI  - Edgeless graphs are the only universal fixers
JO  - Czechoslovak Mathematical Journal
PY  - 2014
SP  - 833
EP  - 843
VL  - 64
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0136-3/
DO  - 10.1007/s10587-014-0136-3
LA  - en
ID  - 10_1007_s10587_014_0136_3
ER  - 
%0 Journal Article
%A Wash, Kirsti
%T Edgeless graphs are the only universal fixers
%J Czechoslovak Mathematical Journal
%D 2014
%P 833-843
%V 64
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0136-3/
%R 10.1007/s10587-014-0136-3
%G en
%F 10_1007_s10587_014_0136_3

[1] Burger, A. P., Mynhardt, C. M.: Regular graphs are not universal fixers. Discrete Math. 310 (2010), 364-368. | DOI | MR | Zbl

[2] Cockayne, E. J., Gibson, R. G., Mynhardt, C. M.: Claw-free graphs are not universal fixers. Discrete Math. 309 (2009), 128-133. | DOI | MR | Zbl

[3] Gibson, R. G.: Bipartite graphs are not universal fixers. Discrete Math. 308 (2008), 5937-5943. | DOI | MR | Zbl

[4] Gu, W.: Communication with S. T. Hedetniemi. Southeastern Conference on Combinatorics, Graph Theory, and Computing. Newfoundland, Canada, 1999.

[5] Gu, W., Wash, K.: Bounds on the domination number of permutation graphs. J. Interconnection Networks 10 (2009), 205-217. | DOI

[6] Hartnell, B. L., Rall, D. F.: On dominating the Cartesian product of a graph and $K_2$. Discuss. Math., Graph Theory 24 (2004), 389-402. | DOI | MR | Zbl

[7] Mynhardt, C. M., Xu, Z.: Domination in prisms of graphs: universal fixers. Util. Math. 78 (2009), 185-201. | MR | Zbl

Cité par Sources :