Neighbor-scattering number in regular graphs

Network reliability is an important issue in the area of distributed computing. Most of the early work in this area takes a probabilistic approach to the problem. However, sometimes it is important to incorporate subjective reliability estimate s into the measure. To serve this goal, we propose the use of neighbor-scattering number, a measure of graph vulnerability. In this paper, we give a complete characterization of all minimal (1 - k)-neighbor-scattered graph which are k-regular and contain a k-clique.