Distance center and centroid of a median graph (Q1092069)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Distance center and centroid of a median graph |
scientific article |
Statements
Distance center and centroid of a median graph (English)
0 references
1987
0 references
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.
0 references
median
0 references
median graph
0 references
minimum distance
0 references
distance center
0 references
branch weight
0 references
centroid
0 references