Domination Integrity of Splitting Graph of Path and Cycle

If is a dominating set of a connected graph then the domination integrity is the minimum of the sum of two parameters, the number of elements in and the order of the maximum component of . We investigate domination integrity of splitting graph of path and cycle . This work is an effort to relate network expansion and vulnerability parameter. 1. Introduction The stability of a communication network is of prime importance for any network designer. A shrinking network eventually loses links or nodes, its effectiveness is continuously decreasing and network becomes vulnerable. Many graph theoretic parameters have been introduced for the measurement of vulnerability. Some of them are connectivity, toughness, integrity, and rupture degree. The integrity of a graph is one of the well explored concepts which was introduced by Barefoot et al. [1]. Definition 1. The integrity of a graph is denoted by and defined by = , where is the order of a maximum component of . Definition 2. An -set of is any (proper) subset of for which . The integrity of the complete graph , path , cycle , star , complete bipartite graph , and power graph of cycle were discussed by Barefoot et al. [1, 2] while Goddard and Swart [3, 4] have investigated the bounds for integrity of graphs and its complement. They have also investigated the integrity of graphs in the context of some graph operations. The integrity of middle graphs is discussed by Mamut and Vumar [5] while integrity of total graphs is discussed by Dündar and Ayta？ [6]. Definition 3. A set of vertices in a graph is called dominating set if every vertex is either an element of or is adjacent to an element of . Definition 4. The domination number of a graph equals the minimum cardinality of minimal dominating set of graph . If is any minimal dominating set and if the order of the largest component of is small, then the removal of will crash the communication network. Considering this aspect, the concept of domination integrity was introduced by Sundareswaran and Swaminathan [7]. Definition 5. The domination integrity of a connected graph is denoted as = is a dominating set}, where is the order of a maximum component of . Sundareswaran and Swaminathan [8] have investigated domination integrity of middle graph of some graphs while Vaidya and Kothari [9] have discussed domination integrity of a graph obtained by duplication of an edge by a vertex and duplication of vertex by an edge in and . In the present work we investigate domination integrity of splitting graphs of path and cycle. Definition 6. For a graph the splitting graph of