Sufficient conditions for maximally connected dense graphs (Q1086585)

This paper is motivated by the problem of finding the maximum number n(\(\Delta\),D) of vertices in a(\(\Delta\),D) graph, the latter being a graph of given maximum degree \(\Delta\) and given diameter D. Moore has shown that n(\(\Delta\),D)\(\leq (\Delta (\Delta -1)^ D-2)/(\Delta -2)\) for \(\Delta >2\) and it is known that graphs attaining Moore's bound can exist only if D is 2 and \(\Delta\) is 3, 7 or 57. In this paper, the authors study the connectivity \(\kappa\) and edge-connectivity \(\lambda\) of (\(\Delta\),D) graphs for which the number n of vertices is close to n(\(\Delta\),D). Among the results proved is that \(\kappa\) is maximal, that is, equals the minimum degree \(\delta\) if n exceeds (\(\delta\)-1)\((\Delta -1)^{D-1}+2\) and \(\Delta\) exceeds 2. Other results give conditions for \(\kappa\) or \(\lambda\) to equal \(\delta\) in terms of the diameter and the girth.