Volume :8 , Issue :4 ,Page :265 - 274

Abstract :A set D of a graph G = (V, E) is a dominating set if every vertex in V(G) – D is adjacent to some vertex in D. The domination number ? (G) of G is the minimum cardinality of a dominating set. A dominating set D is called a complementary tree nil dominating set, if the induced subgraph < V(G) – D > is a tree and the set V(G) – D is not a dominating set. The minimum cardinality of a complementary tree nil dominating set is called the complementary tree nil domination number of G and is denoted by ? ctnd(G). The minimum number of colours required to colour all the vertices such that adjacent vertices do not receive the same colour is chromatic number ? (G). In this paper, an upper bound for the sum of the complementary tree nil domination number and chromatic number of a graph is found and the corresponding extremal graphs are characterized.