pith. sign in

arxiv: 1308.5466 · v1 · pith:SBEA34DOnew · submitted 2013-08-26 · 🧮 math.CO

Edgeless graphs are the only universal fixers

classification 🧮 math.CO
keywords universaldominationedgelessfixersgraphgraphsnumberonly
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.