Domination in transformation graph GxY-*

摘要

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 CzY- of G is the graph with vertex set V(G) U E(G) in which the vertex a and /3 are joined by an edge if one of the following conditions holds: (i) a, 0 E V(G),and a and /3 are adjacent in G if x = +, and a and /3 are not adjacent in G if x = (ii) a, /3 E E(G), and a and /3 are adjacent in G if Y = +, and a and /3 are not adjacent in G if y = (iii) one of a and /3 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(Gx71-) < 3 for a nonempty graph G and for any x, y E {+, -}, with a unified proof. Furthermore, we characterize the graph G with -y(GsY-) = k for each k E {1, 2, 3}, where x, y E {+, -}. As a consequence, a minimum dominating set of GxY- can be found in polynomial time (in linear time in some cases).