On long-standing open problem: What is the maximum average distance among all graphs of given order and diameter/radius

In the classical paper, [J. Plesnik, Critical graphs of given diameter, Acta Fac. Rerum Natur. Univ. Comenianae Math. 30 (1975) 71–93] following problem was presented: problem 1: What is the maximum average distance among all graphs of given order and diameter? This problem is one of the well-known and long-standing open problems in distance graph theory. Since there exist a close relation between diameter and radius of graphs, it was natural for researchers to ask above-mentioned question for radius of graphs. problem 2: What is the maximum average distance among all graphs of given order and radius? In this paper, we apply Djokovic-Winkler’s relation to find a general func- tion for average distance of graphs. Then, by using various cut methods and optimization techniques, we answer and characterize the first problem when the given graph is a tree and diameter d is double of radius r. When d = 2r􀀀1 we characterize the trees with maximum average distance and find the maximum value or satisfactory near maximum value of average distance. Moreover, we solve the second problem in general graphs and characterize the graphs with maximum average distance of given order and radius.