Domination integrity of some graph classes

Ege University Faculty of Science, Department of Mathematics, 35100 Bornova Izmir, Turkey

^* Corresponding author: elgin.kilic@ege.edu.tr; elginkilic@gmail.com

Received: 6 March 2017
Accepted: 4 September 2018

Abstract

The stability of a communication network has a great importance in network design. There are several vulnerability measures used to determine the resistance of network to the disruption in this sense. Domination theory provides a model to measure the vulnerability of a graph network. A new vulnerability measure of domination integrity was introduced by Sundareswaran in his Ph.D. thesis (Parameters of vulnerability in graphs (2010)) and defined as DI(G) = min{|S| + m(G − S):S ∈ V(G)} where m(G − S) denotes the order of a largest component of graph G − S and S is a dominating set of G. The domination integrity of an undirected connected graph is such a measure that works on the whole graph and also the remaining components of graph after any break down. Here we determine the domination integrity of wheel graph W_1,n, Ladder graph L_n, S_m,n, Friendship graph F_n, Thorn graph of P_n and C_n which are commonly used graph models in network design.