Neighborhood Connected Domination and Colouring in Graphs
C. Sivagnanam · International Journal of Mathematics and Soft Computing · 2014
A dominating set S of a connected graph G = (V,E) is a neighborhood connected dominating set (ncd-set) if the induced subgraph 〈N(S) 〉 of G is connected. The neighborhood connected domination number γnc(G) is the minimum cardinality of a ncd-set. The minimum number of colours required to colour all the vertices such that no two adjacent vertices have same colour is the chromatic number χ(G) of G. In this paper we find an upper bound for sum of the ncd-number and chromatic number and characterize the corresponding extremal graphs.