# Edgeless graphs are the only universal fixers

• Volume: 64, Issue: 3, page 833-843
• ISSN: 0011-4642

top

## Abstract

top
Given two disjoint copies of a graph $G$, denoted ${G}^{1}$ and ${G}^{2}$, and a permutation $\pi$ of $V\left(G\right)$, the graph $\pi G$ is constructed by joining $u\in V\left({G}^{1}\right)$ to $\pi \left(u\right)\in V\left({G}^{2}\right)$ for all $u\in V\left({G}^{1}\right)$. $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\left(G\right)$. 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.

## How to cite

top

Wash, Kirsti. "Edgeless graphs are the only universal fixers." Czechoslovak Mathematical Journal 64.3 (2014): 833-843. <http://eudml.org/doc/262156>.

@article{Wash2014,
abstract = {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.},
author = {Wash, Kirsti},
journal = {Czechoslovak Mathematical Journal},
keywords = {universal fixer; domination; universal fixer; domination number; prism},
language = {eng},
number = {3},
pages = {833-843},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Edgeless graphs are the only universal fixers},
url = {http://eudml.org/doc/262156},
volume = {64},
year = {2014},
}

TY - JOUR
AU - Wash, Kirsti
TI - Edgeless graphs are the only universal fixers
JO - Czechoslovak Mathematical Journal
PY - 2014
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 64
IS - 3
SP - 833
EP - 843
AB - 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.
LA - eng
KW - universal fixer; domination; universal fixer; domination number; prism
UR - http://eudml.org/doc/262156
ER -

## References

top
1. Burger, A. P., Mynhardt, C. M., 10.1016/j.disc.2008.09.016, Discrete Math. 310 (2010), 364-368. (2010) Zbl1216.05098MR2563053DOI10.1016/j.disc.2008.09.016
2. Cockayne, E. J., Gibson, R. G., Mynhardt, C. M., 10.1016/j.disc.2007.12.053, Discrete Math. 309 (2009), 128-133. (2009) Zbl1219.05116MR2475005DOI10.1016/j.disc.2007.12.053
3. Gibson, R. G., 10.1016/j.disc.2007.11.006, Discrete Math. 308 (2008), 5937-5943. (2008) Zbl1181.05068MR2464884DOI10.1016/j.disc.2007.11.006
4. Gu, W., Communication with S. T. Hedetniemi, Southeastern Conference on Combinatorics, Graph Theory, and Computing. Newfoundland, Canada, 1999.
5. Gu, W., Wash, K., 10.1142/S0219265909002522, J. Interconnection Networks 10 (2009), 205-217. (2009) DOI10.1142/S0219265909002522
6. Hartnell, B. L., Rall, D. F., 10.7151/dmgt.1238, Discuss. Math., Graph Theory 24 (2004), 389-402. (2004) Zbl1063.05107MR2120063DOI10.7151/dmgt.1238
7. Mynhardt, C. M., Xu, Z., Domination in prisms of graphs: universal fixers, Util. Math. 78 (2009), 185-201. (2009) Zbl1284.05199MR2499846

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.