Studies on some domination parameters in graphs

Abstract

By a graph G = (V,E), we mean a finite undirected connected graph with neither loops nor multiple edges. In chapter 1, we collect some basic definitions and theorems on graphs which are needed for the subsequent chapters. One of the fastest growing areas with in graph theory is the study of domination. A dominating set S of G is called a connected dominating set if the induced subgraph and#10216;Sand#10217; is connected. The minimum cardinality of a connected dominating set of G is called the connected domination number of G and is denoted by and#947;c(G). In chapter 2, we introduce the concept of neighborhood connected perfect domination and initiate a study of corresponding parameter. The minimum cardinality of a ncpd-set of G is called the neighborhood connected perfect domination number of G and is denoted by and#947;ncp(G). Several results on this parameter are presented in chapter 2. In chapter 3, we initiate a study of neighborhood connected 2-dominating set and neighborhood connected 2-domination number of a graph. In chapter 4, we introduce the concept of neighborhood connected edge domination and initiate a study of corresponding parameter. The vertex connectivity number and#954;(G) of a graph G is the minimum number of vertices whose removal results in a disconnected or trivial graph. In chapter 5, we find the upper bound for the sum and#947;r+and#954; and characterize the corresponding extremal graphs. Also we find the upper bound for sums and#947;2nc+and#954; and and#947;ncp+and#954; and characterize the corresponding extremal graphs. newline