IJPAM: Volume 70, No. 3 (2011)



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.
Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2011
Volume: 70
Issue: 3