| Title:
|
Edgeless graphs are the only universal fixers (English) |
| Author:
|
Wash, Kirsti |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
64 |
| Issue:
|
3 |
| Year:
|
2014 |
| Pages:
|
833-843 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
universal fixer |
| Keyword:
|
domination |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 06391529 |
| idMR:
|
MR3298564 |
| DOI:
|
10.1007/s10587-014-0136-3 |
| . |
| Date available:
|
2014-12-19T16:16:50Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144062 |
| . |
| Reference:
|
[1] Burger, A. P., Mynhardt, C. M.: Regular graphs are not universal fixers.Discrete Math. 310 (2010), 364-368. Zbl 1216.05098, MR 2563053, 10.1016/j.disc.2008.09.016 |
| Reference:
|
[2] Cockayne, E. J., Gibson, R. G., Mynhardt, C. M.: Claw-free graphs are not universal fixers.Discrete Math. 309 (2009), 128-133. Zbl 1219.05116, MR 2475005, 10.1016/j.disc.2007.12.053 |
| Reference:
|
[3] Gibson, R. G.: Bipartite graphs are not universal fixers.Discrete Math. 308 (2008), 5937-5943. Zbl 1181.05068, MR 2464884, 10.1016/j.disc.2007.11.006 |
| Reference:
|
[4] Gu, W.: Communication with S. T. Hedetniemi.Southeastern Conference on Combinatorics, Graph Theory, and Computing. Newfoundland, Canada, 1999. |
| Reference:
|
[5] Gu, W., Wash, K.: Bounds on the domination number of permutation graphs.J. Interconnection Networks 10 (2009), 205-217. 10.1142/S0219265909002522 |
| Reference:
|
[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. Zbl 1063.05107, MR 2120063, 10.7151/dmgt.1238 |
| Reference:
|
[7] Mynhardt, C. M., Xu, Z.: Domination in prisms of graphs: universal fixers.Util. Math. 78 (2009), 185-201. Zbl 1284.05199, MR 2499846 |
| . |
