A proof of the universal fixer conjecture

Abstract

For a given graph G = (V, E) and permutation π: V → V the prism πG of G is denned as follows: V(πG) = V(G) ∪ V(G'), where G' is a copy of G, and E(πG) = E(G)∪E(G')∪Mπ, where Mπ = {uv': u ∈ V(G), v = π(u)} and v' denotes the copy of v in G'. The graph G is called a universal fixer if λ(πG) = π(G) for every permutation π. The idea of universal fixers was introduced by Burger, Mynhardt and Weakley in 2004. In this work we prove that the edgeless graphs K_n are the only universal fixers. © 2018 Utilitas Mathematica Publishing Inc. All rights reserved.