The common-neighbourhood of a graph

Abstract

The vulnerability measures on 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 measures. In this work we define and examine the Common-neighbourhood of a connected graph as a new global connectivity measure. It takes account the neighbourhoods of all   pairs of vertices. We show that, for connected graphs G₁ and G₂ of order n, if the dominating number of G₁ is bigger than the dominating number of G₂, then the common- neighbourhood of G₁ is less than the common-neighbourhood of G₂. We prove some theorems on common-neighbourhood of a graph.