The search functionality is under construction.

The search functionality is under construction.

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 *G* as a generalization of the blocks of *G*, where *G*; and define the *G* as a generalization of the centroid of *G*. First, we prove that the *G* is included in an *G*. This is a generalization of the above theorems concerning centroid, by Jordan and Truszczynski. Secondly, we define the *G* as a generalization of the *k*-centrum of *G* and prove some theorems concerning the location of *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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

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 *G* as a generalization of the blocks of *G*, where *G*; and define the *G* as a generalization of the centroid of *G*. First, we prove that the *G* is included in an *G*. This is a generalization of the above theorems concerning centroid, by Jordan and Truszczynski. Secondly, we define the *G* as a generalization of the *k*-centrum of *G* and prove some theorems concerning the location of *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 *G* as a generalization of the blocks of *G*, where *G*; and define the *G* as a generalization of the centroid of *G*. First, we prove that the *G* is included in an *G*. This is a generalization of the above theorems concerning centroid, by Jordan and Truszczynski. Secondly, we define the *G* as a generalization of the *k*-centrum of *G* and prove some theorems concerning the location of *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 *G* as a generalization of the blocks of *G*, where *G*; and define the *G* as a generalization of the centroid of *G*. First, we prove that the *G* is included in an *G*. This is a generalization of the above theorems concerning centroid, by Jordan and Truszczynski. Secondly, we define the *G* as a generalization of the *k*-centrum of *G* and prove some theorems concerning the location of *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 -