On a Relation between -Centroid and -Blocks in a Graph

Masashi TAKEUCHI  Shoji SOEJIMA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E83-A   No.10   pp.2009-2014
Publication Date: 2000/10/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
Keyword: 
graph,  distance,  -block,  -centroid,  -centrum,  

Full Text: PDF(386.9KB)>>
Buy this Article




Summary: 
The problem of finding the location of the center and the problem of finding the median in a graph are important and basic among many network location problems. In connection with these two problems, the following two theorems are well-known. One is proved by Jordan and Sylvester, and it shows that the center of every tree consists of either one vertex or two adjacent vertices. The other is proved by Jordan and it shows that the centroid (median) of every tree consists of either one vertex or two adjacent vertices. These theorems have been generalized by many researchers so far. Harary and Norman proved that the center of every connected graph G lies in a single block of G. Truszczynski proved that the median of every connected graph G lies in a single block of G. Slater defined k-centrum, which can express both center and median, and proved that the k-centrum of every tree consists of either one vertex or two adjacent vertices. This paper discusses generalization of these theorems. We define the -blocks of a graph G as a generalization of the blocks of G, where is a subset of the vertex set of G; and define the -centroid of G as a generalization of the centroid of G. First, we prove that the -centroid of G is included in an -block of G. This is a generalization of the above theorems concerning centroid, by Jordan and Truszczynski. Secondly, we define the -centrum of G as a generalization of the k-centrum of G and prove some theorems concerning the location of -centrum. Using one of theorems proved here, we can easily obtain the theorem showing that the k-centrum of every connected graph G lies in a single block of G. This theorem is a generalization of the above theorem by Slater.