کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427750 | 686551 | 2012 | 4 صفحه PDF | دانلود رایگان |
Let G=(V,E)G=(V,E) be a connected graph on n vertices. The proximity π(G)π(G) of G is the minimum average distance from a vertex of G to all others. The eccentricity e(v)e(v) of a vertex v in G is the largest distance from v to another vertex, and the average eccentricity ecc(G)ecc(G) of the graph G is 1n∑v∈V(G)e(v). Recently, it was conjectured by Aouchiche and Hansen (2011) [3] that for any connected graph G on n⩾3n⩾3 vertices, ecc(G)−π(G)⩽ecc(Pn)−π(Pn)ecc(G)−π(G)⩽ecc(Pn)−π(Pn), with equality if and only if G≅PnG≅Pn. In this paper, we show that this conjecture is true.
► Two characterizations for a vertex v being a centroidal vertex in a tree are given.
► A kind of transformation for a tree is introduced.
► A conjecture concerning proximity and average eccentricity is proved.
Journal: Information Processing Letters - Volume 112, Issue 10, 31 May 2012, Pages 392–395