Domination parameters in Mycielski graphs

Abstract

For a graph G, let M(G) denote the Mycielski graph of G. The t-th iterated Mycielski graph of G, M^t(G), is defined recursively by M ⁰(G) = G and M^t(G) = M(M^t-1(G)) for t ≥ 1. Let γ(G), i(G), γ_t(G), γ_p(G) and γ_c(G) denote the domination number, independent domination number, total domination number, paired domination number and connected domination number of G, respectively. Firstly, we prove that γ(M(G)) = γ(G) + 1, i(M(G)) = i(G) + 1 and γ_t(M(G)) = γ_t(G) + 1. Secondly, we prove that either γ _p(M(G)) = γ_p(G) or γ_p(M(G)) = γ_p(G) + 2 and characterize the graphs with γ _p(G) = γ_p(M(G)). Finally, we discuss the connected domination number of M(G).