For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On a Relation between -Centroid and -Blocks in a Graph
Masashi TAKEUCHI Shoji SOEJIMA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/10/25
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
graph, distance, -block, -centroid, -centrum,
Full Text: PDF(386.9KB)>>
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.