Domination in prisms of graphs: Universal fixers Mynhardt C.M.aSend mail to Mynhardt C.M.;Xu, Zhixiab, cSend mail to Xu Z.

Abstract

For any permutation π of the vertex set of a graph G, the prism of G with respect to π is the graph πG obtained from two copies G′ and G′′ of G by joining u ε V(G′) and v ε V(G′′) if and only if v = π(u). It is easy to see that γ(G) ≤ γ(πG) ≤ 2γ(G) for all permutations π of V(G), where γ(G) denotes the domination number of G. If γ(πG) = γ(G) for all π then G is called a universal γ-fixer. The edgeless graphs K̄_n are examples of universal γ-frxers. We conjecture that these graphs are the only universal fixers and prove that the conjecture is true for several classes of graphs, including fc-regular graphs for k ≤ 4, graphs with minimum degree less than three, and graphs with domination number at most three.