Secure domination in transformation graphs

Abstract

A secure dominating set S of a graph G is a dominating set with the property that for every vertex v and#8712; V(G)\S, there exists a neighbour u and#8712; S such that (S and#8746;{v})\{u} is a dominating set. The smallest cardinality of such a set is called the secure domination number of G denoted by and#947;s(G). The transformation graph Gxyz is constructed newlinefrom a graph G and the vertex set of Gxyz is V(G) and#8746; E(G). For any two vertices a, b in V (Gxyz), the associativity of a and b is - if they are not adjacent nor incident in G and + otherwise. If both a and b are in V(G) (or both a and b are in E(G), or if one of a and b is in V(G) while the other is in E(G)), then the vertices a and b correspond to the frst term x (the second term y or the third term z, respectively) of xyz. Two vertices a and b of Gxyz are connected by an edge, if their associativity in G is compatible with the corresponding term of xyz. The permutation set of {+, and#8722;} taken three at a time corresponds to the value of xyz. We study the eight diand#64256;erent transformation graphs of G. In this study, we characterize graphs for which the secure domination number of the transformation graph Gxy+ is 1 or 2. Also we prove that for any connected graph G newlinewith at least 4 pendant vertices, the secure domination number is greater than or equal to the secure domination number of the transformation graph Gand#8722;++. We also fnd a bound for the secure domination number of Gand#8722;and#8722;+ when G is a tree. We have studied this concept for diand#64256;erent classes of graphs and obtained results in terms of the subgraphs of the transformation graphs. This includes the given graph, line graph and subdivision graph. Eventually, G+++ is the total graph of G, and Gand#8722;and#8722;and#8722; is the complement of the total newlinegraph of G. Therefore, we investigate the necessary and sufcient conditions for a graph to have and#947;s(G) equal to 1 or 2 in the case of disconnected graphs. Further, we found an additional case for which the bound, and#947;s(G) and#8804; n 2 holds true.

Description

Keywords

Citation

item.page.endorsement

item.page.review

item.page.supplemented

item.page.referenced