Edgeless graphs are the only universal fixers

Given two disjoint copies of a graph $G$, denoted $G^1$ and $G^2$, and a permutation $π$ of $V(G)$, the graph $πG$ is constructed by joining $u \in V(G^1)$ to $π(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 $πG$ is equal to the domination number of $G$ for all $π$ 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.

No reviews yet.

No comments yet.