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

概要

論文の詳細を見る
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.
社団法人電子情報通信学会の論文
2000-10-25

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

スポンサーリンク

概要

著者

関連論文

スポンサーリンク