Domination in transformation graph Gxy

Abstract

Let G = (V(G), E(G)) be a simple undirected graph of order n and size m, and x, y, z be three variables taking value + or-. The transformation graph Gxv of G is the graph with vertex set V(G) U E(G) in which the vertex a and ? are joined by an edge if one of the following conditions holds: (i) a,p V(G),and a and p are adjacent in G if x = +, and a and p are not adjacent in G if x =-, (ii) a,9 E((T), and a and p are adjacent in G if Y = +, and a and p are not adjacent in G if y =-, (iii) one of a and P is in V(G) and the other is in E(G), and they are not incident in G. In this note, it is shown that ry(Gxy) < 3 for a nonempty graph G and for any x,y 6 {+,-}, with a unified proof. Furthermore, we characterize the graph G with 7(Gxy) = k for each k {1,2,3}, where x,y £ {+,-}• As a consequence, a minimum dominating set of Gxy can be found in polynomial time (in linear time in some cases). © 2019 Utilitas Mathematica Publishing Inc.. All rights reserved.