THE MEDIUM DOMINATION NUMBER OF A GRAPH
Duygu VARGÖR, Pınar Erbay Dündar · International Journal of Pure and Apllied Mathematics · 2011
In a communication network resistance of network is re- sponse to any disruption in some of stations or lines. Vulnerability values measures resistance of network in disruption of some vertices until com- munication breakdown. A network can be modeled by a graph whose vertices represent stations and whose edges represent relation between ver- tices. In graph theory, some stability measures have been studied widely such as connectivity, edge-connectivity, integrity, tenacity, vertex covering and dom- ination. These parameters take consideration into 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 medium domination of a graph and study on some graph classes. The medium domination is a notion which uses neighborhood of each pair of vertices. The main idea of this parameter is that each u,v 2 V must be protected. So it is needed to examine how many vertices are capable of dominating both of u and v. Also total 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 other vulnerability measures and give an algorithm with complexity of O(n 2 ).