The Average-Dominating of a graph

摘要

The vulnerability is one of the most important concepts in network design. Vulnerability can be considered as the resistance of the network after any breakdown in its nodes or links. Since any network can be modelled by a graph, vulnerability parameters on graphs also work on network types. The vertices and the edges of a graph correspond to the processors and the links of the network, respectively. The measure parameters about the vulnerability of a connected graph which are mostly used and known are based on the Neighbourhood concept. Neighbour-integrity, edge-integrity and accessibility number are some of these parameters. In this work we defined and examined the Average-Dominating of a connected graph as a new global connectivity measure. It takes account the neighbourhoods of all pairs of vertices. First we define the pair dominating of any two vertices such as u and v in a graph as to be the maximum number of vertices which dominate both u and v in G. It is denoted by D(u,v). Then latter we define the average dominating of G denoted by D(G) as, where G is a graph of order n.