The average diameter and its estimation in nonlinear structures

We suggested to use average diameter as another, and a more global, measure ment of the data transfer capability of network structures(1). In terms of graph theory, a general strategy to derive the average diameter of a graph is to apply combinatorial and other techniques to count the total number of simple paths between any two arbitrary vertices in the associated graph, c alculate the sum of their lengths, and then divide the latter by the former . Following this approach, average diameters of various linear network stru ctures, i.e., tree structures, and some of the nonlinear structures, such a s rings, have been obtained. However, for a general nonlinear structure, because of the involved combina torial complexity, a precise combinatorial and/or asymptotic analysis of it s average diameter is quite difficult and even impractical. In this paper, after a brief review of the linear case, we discuss the derivation of avera ge diameter and its estimation, via the notion of average distance, for non linear structures; This subject should be both challenging and interesting for the graph theoreticians, as well, as it poses another sizing problem of measuring various graph structures, in addition to using the existing ones such as diameter, girth, etc. (C) 2000 Elsevier Science Ltd. All rights re served.