Outer-connected domination in graphs

Abstract

A set S of vertices in a graph G = (V, E) is an outerconnected dominating set (OCDS) of G if 5 is a dominating set of G and G[V - S] is connected. The outer-connected domination number of G is the minimum cardinality of an OCDS of G. In this paper we characterize the graphs with large outer-connected domination number. Also, we give Nordhaus-Gaddum-type inequality on outer-connected domination and characterize the graphs with the right equality.