Edgeless graphs are the only universal fixers
Kirsti Wash · Czechoslovak Mathematical Journal · 2014
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 ∈ V (G 1) to π(u) ∈ V (G 2) for all u ∈ 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.