• COMPLEMENTARY TREE NIL DOMINATION NUMBER AND CONNECTIVITY OF GRAPHS

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 also 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. The connectivity (G) of G is the minimum number of vertices whose removal results in a disconnected or trivial graph. In this paper, an upper bound for the sum of the complementary tree nil domination number and connectivity of a graph is found and the corresponding extremal graphs are characterized.