# IJPAM: Volume 70, No. 3 (2011)

**THE MEDIUM DOMINATION NUMBER OF A GRAPH**

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.**

**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