Signed domination and Mycielski’s structure in graphs

¹ Department of Irrigation and Reclamation Engineering, University of Tehran, Tehran, I.R. Iran
² Department of Basic Science, Imam Khomeini International University, Qazvin, I.R. Iran
³ Department of Mathematics, University of West Georgia, Carrollton, GA 30118, USA

^* Corresponding author: a.ghameshlou@ut.ac.ir

Received: 9 July 2019
Accepted: 13 November 2019

Abstract

Let G = (V, E) be a graph. The function f : V(G) → {−1, 1} is a signed dominating function if for every vertex v ∈ V(G), ∑_x∈NG[v] f(x)≥1. The value of ω(f) = ∑_x∈V(G) f(x) is called the weight of f. The signed domination number of G is the minimum weight of a signed dominating function of G. In this paper, we initiate the study of the signed domination numbers of Mycielski graphs and find some upper bounds for this parameter. We also calculate the signed domination number of the Mycielski graph when the underlying graph is a star, a wheel, a fan, a Dutch windmill, a cycle, a path or a complete bipartite graph.