Edgeless graphs are the only universal fixers

Kirsti Wash
Trinity College

PDF

Minisymposium: GRAPH DOMINATION

Content: 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, Gu conjectured that the only universal fixers are the edgeless graphs. Over the next decade, several classes of connected graphs were identified as not containing any universal fixers. In this talk, we show explicitly how to partition a graph $G$ and define a permutation on $V(G)$ to guarantee that edgeless graphs are the only universal fixers.

Back to all abstracts