Vol. LXXV, 2(2006), pp. 149–152 ON (k, l)-RADIUS OF RANDOM GRAPHS

Abstract. We introduce the concept of (k, l)-radius of a graph and prove that for any fixed pair k, l the (k, l)-radius is equal to 2 �k � �l � − for almost all graphs. 2 2 Since for k = 2 and l = 0 the (k, l)-radius is equal to the diameter, our result is a generalization of the known fact that almost all graphs have diameter two. All graphs in this note are finite, undirected and simple. As usual, by distance between two vertices in a graph we mean the minimum length of a path connecting them. Then the diameter is the maximum distance between two vertices. The transmission of the graph, also called a distance of the graph, is defined as the sum of distances between all pairs of vertices (for general properties of the distance see [4]). The concepts of diameter and distance were generalized by Goddard, Swart and Swart in [3] by introducing the k-diameter as follows. The distance of k vertices dk(v1, v2,..., vk) is the sum of distances between all pairs of vertices from {v1, v2,..., vk}. The k-diameter is the maximum distance of a set of k vertices. Hence the 2-diameter is the usual diameter and if n is the order of the graph, the n-diameter is the distance of the graph. In this note we use the definition of distance of a set of k vertices to define (k, l)-eccentricity and (k, l)-radius. We study (k, l)-radius of random graphs and determine the value of this parameter for almost all graphs in a probability space. We also discus the relationship between the (k, l)-radius and the k-diameter of a graph. Let S be a set of l vertices, 0 ≤ l ≤ k. We define (k, l)-eccentricity of S, ek,l(S), as the maximum distance of k vertices u1, u2,..., uk, such that S ⊆ {u1, u2,..., uk}. In symbols, ek,l(S) = ma