Duygu Vargör, Pınar Dündar
Department of Mathematics
Faculty of Science
Ege University
Bornova, 35100, Izmir, TURKEY

Abstract. In a communication network the resistance of network is the response to any disruption in some of stations or lines. Vulnerability values measures the resistance of network in disruption of some vertices until communication breakdown. A network can be modeled by a graph whose vertices represent the stations and whose edges represent the relation between the vertices. In graph theory, some stability measures have been studied widely such as connectivity, edge-connectivity, integrity, tenacity, vertex covering and domination. These parameters take consideration into the neighborhood of edges and vertices. In a graph each vertex is capable of protecting every vertex in its neighborhood and in domination every vertex is required to be protected. In this paper, for any connected, undirected, loopless graph we define the medium domination number of a graph and study on some graph classes. The medium domination number is a notion which uses neighborhood of each pair of vertices. The main idea of this parameter is that each must be protected. So it is needed to examine how many vertices are capable of dominating both of and . Also the total number of vertices that dominate every pair of vertices and average value of this is defined as ``the medium domination number'' of a graph. We establish some new results and relation with the other vulnerability measures and give an algorithm with the complexity of .

Received: October 31, 2010

AMS Subject Classification: 05C05, 05C07, 05C69

Key Words and Phrases: communication network, vulnerability, neighborhood, domination number

Download paper from here.