Edgeless graphs are the only universal fixers
Czechoslovak Mathematical Journal (2014)
- Volume: 64, Issue: 3, page 833-843
- ISSN: 0011-4642
Access Full Article
top
Abstract
topHow to cite
topWash, 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- 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
- 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
- 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
- Gu, W., Communication with S. T. Hedetniemi, Southeastern Conference on Combinatorics, Graph Theory, and Computing. Newfoundland, Canada, 1999.
- Gu, W., Wash, K., 10.1142/S0219265909002522, J. Interconnection Networks 10 (2009), 205-217. (2009) DOI10.1142/S0219265909002522
- Hartnell, B. L., Rall, D. F., 10.7151/dmgt.1238, Discuss. Math., Graph Theory 24 (2004), 389-402. (2004) Zbl1063.05107MR2120063DOI10.7151/dmgt.1238
- Mynhardt, C. M., Xu, Z., Domination in prisms of graphs: universal fixers, Util. Math. 78 (2009), 185-201. (2009) Zbl1284.05199MR2499846
NotesEmbed ?
topYou 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.