• DOMINATION SUBDIVISION STABLE GRAPHS

Abstract

A set of vertices D in a graph G = (V, E) is a dominating set if every vertex of V – D is adjacent to some vertex of D. If D has the smallest possible cardinality of any dominating set of G, then D is called a minimum dominating set -abbreviated MDS. The cardinality of any MDS for G is called the domination number of G and it is denoted by  (G). A graph G is said to be domination subdivision stable (DSS), if the  - value of G does not change by subdividing any edge of G. In this paper, we have obtained necessary and sufficient condition for a graph G to be a DSS graph. We have discussed conditions under which a graph is DSS and not DSS. We have generated new DSS graphs from existing ones and proved that every graph G is an induced sub graph of DSS graph.