SPECTRAL ASPECTS OF AVERAGE VERTEX CONNECTIVITY OF A GRAPH

Abstract

The measures of global connectivity such as graph integrity and toughness have non-polynomial time complexities. This has led to the development of global average graph vertex connectivity measures that are dependent on combinatoric counting of number of internally disjoint paths in a graph. Many results related to average vertex connectivity have been found. This study develops a spectral form of average vertex connectivity, together with its upper bounds. Using trees, we demonstrate that the new definition and its upper bounds are more related to ordinary graph parameters.