AVERAGE LOWER DOMINATION NUMBER IN GRAPHS

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.