IJPAM: Volume 70, No. 3 (2011)
Department of Mathematics
Faculty of Science
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.
Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395