NEIGHBOURHOOD CONNECTED AND DISCONNECTED DOMINATION IN CIRCULAR-ARC GRAPHS USING ALGORITHMS

Abstract

A dominating set S of a connected graph G is called a neighborhood connected dominating set (ncd-set) if the induced sub-graph 〈N(S)〉 is connected. If the induced sub-graph 〈N(S)〉 is disconnected, then S is called neighbourhood disconnected dominating set. In this paper we develop algorithms to find neighborhood connected dominating set and neighborhood disconnected dominating set for circular-arc graphs.