
For FullText 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
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E83A
No.10
pp.20092014 Publication Date: 2000/10/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: PAPER Category: Graphs and Networks Keyword: graph, distance, block, centroid, centrum,
Full Text: PDF(386.9KB)>>
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 wellknown. 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 kcentrum, which can express both center and median, and proved that the kcentrum 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 kcentrum 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 kcentrum of every connected graph G lies in a single block of G. This theorem is a generalization of the above theorem by Slater.

