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 q and are joined by an edge if one of the following conditions holds: (I) a, V(G),and a and are adjacent in G if x = +, and a and f3 are not adjacent in G if x =(II) a,0 E(G), and a and p are adjacent in G if Y = +, and a and fi are not adjacent in G if y =(iii) one of a and 0 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 7(Gxy) < 3 for a nonempty graph G and for any x,y {+,-}, with a unified proof. Furthermore, we characterize the graph G with 7(GI>) = 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). © 2020 Utilitas Mathematica Publishing Inc.. All rights reserved.