On a Relation between <sg00041.gif>-Centroid and <sg00041.gif>-Blocks in a Graph

Masashi TAKEUCHI; Shoji SOEJIMA

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

Masashi TAKEUCHI, Shoji SOEJIMA

Full Text Views

0

Cite this

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.10 pp.2009-2014

Publication Date: 2000/10/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Graphs and Networks

Cite this

Copy

Masashi TAKEUCHI, Shoji SOEJIMA, "On a Relation between -Centroid and -Blocks in a Graph" in IEICE TRANSACTIONS on Fundamentals, vol. E83-A, no. 10, pp. 2009-2014, October 2000, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_10_2009/_p

Copy

@ARTICLE{e83-a_10_2009,
author={Masashi TAKEUCHI, Shoji SOEJIMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On a Relation between -Centroid and -Blocks in a Graph},
year={2000},
volume={E83-A},
number={10},
pages={2009-2014},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={October},}

Copy

TY - JOUR
TI - On a Relation between -Centroid and -Blocks in a Graph
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2009
EP - 2014
AU - Masashi TAKEUCHI
AU - Shoji SOEJIMA
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2000
AB - 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.
ER -