AVERAGE LOWER DOMINATION NUMBER IN GRAPHS


Aytac V.

COMPTES RENDUS DE L ACADEMIE BULGARE DES SCIENCES, cilt.65, ss.1665-1674, 2012

  • Cilt numarası: 65 Konu: 12
  • Basım Tarihi: 2012
  • Dergi Adı: COMPTES RENDUS DE L ACADEMIE BULGARE DES SCIENCES
  • Sayfa Sayısı: ss.1665-1674

Özet

In a communication network, several vulnerability measures are used to determine the resistance of the network to disruption of operation after the failure of certain stations or communication links. If we think of a graph as modelling a network, the average lower domination number of a graph is one measure of graph vulnerability. For a vertex v of a graph G = (V, E), the domination number gamma(v)(G) of G relative to v is the minimum cardinality of a dominating set in G that contains v. The average lower domination number of G is gamma(av)(G) = 1/vertical bar V vertical bar Sigma(v is an element of V) gamma(v)(G). In this paper we give the relationships between average lower domination number and some graph parameters, such as diameter, radius, maximum vertex degree, binding number, independence number. Also an algorithm for computing for the average lower domination number of any graph is given.