Study On Some Basic Parameters Of A Graph

Let G be a connected graph on n≥4 vertices with minimum degreeδand radiusr. Thenδr≤(?), with equality if and only if one of the following holds:(1) G is K5,(2) G～= Kn \ M, where M is a perfect matching, if n is even,(3)δ= n - 3 and△≤n -2, if n is odd.This solves a conjecture on the product of the edge-connectivity and radius of agraph, which was posed by Sedlar, Vukiˇcevi′c, Aouchice, and Hansen [14].Using Ore's structural characterization on diameter-maximal graphs, we deter-mine the extremal graphs with the minimum average distance among the graphs withgiven order and diameter, thereby, solving a conjecture of Aouchiche and Hansen [17].