Distance center and centroid of a median graph (Q1092069): Difference between revisions

A vertex t in a connected graph satisfying the equations \(d(a,b)=d(a,b)+d(t,b)\), \(d(a,c)=d(a,t)+d(t,c)\) and \(d(b,c)=d(b,t)+d(t,c)\) is called the median of the vertices a, b and c. (Some terms used in this paper have other meanings in graph theory.) If every triple a, b, c of vertices of a graph G has a unique median, then G is called a median graph. A set A of vertices of a graph G is called a convex of G if A contains all vertices on any shortest a-b path for every pair a,b\(\in A\). The distance of a vertex u in a graph G is the sum of the distances from u to all vertices of G. The vertices of minimum distance are referred to as the distance center of G. A branch of a vertex u is a convex not containing u. The branch weight of u is the maximum number of vertices in a branch of u. The centroid of G consists of all those vertices of minimum branch weight. The author proves that in a median graph, the distance center coincides with the centroid. Further, he shows that the vertices of a centroid form a convex in a connected graph.