La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

On a Relation between -Centroid and -Blocks in a Graph Sur une relation entre -Centroïde et -Blocs dans un graphique

Masashi TAKEUCHI, Shoji SOEJIMA

  • Vues en texte intégral

    0

  • Citer

Résumé:

Le problème de trouver l’emplacement du centre et le problème de trouver la médiane dans un graphique sont importants et fondamentaux parmi de nombreux problèmes de localisation sur réseau. En relation avec ces deux problèmes, les deux théorèmes suivants sont bien connus. L'une d'elles est prouvée par Jordan et Sylvester, et montre que le centre de chaque arbre est constitué soit d'un sommet, soit de deux sommets adjacents. L'autre est prouvé par Jordan et montre que le centroïde (médiane) de chaque arbre est constitué soit d'un sommet, soit de deux sommets adjacents. Ces théorèmes ont été généralisés jusqu’à présent par de nombreux chercheurs. Harary et Norman ont prouvé que le centre de chaque graphe connecté G se trouve dans un seul bloc de G. Truszczynski a prouvé que la médiane de tout graphe connexe G se trouve dans un seul bloc de G. Slater défini k-centrum, qui peut exprimer à la fois le centre et la médiane, et a prouvé que le k-le centre de chaque arbre est constitué soit d'un sommet, soit de deux sommets adjacents. Cet article discute de la généralisation de ces théorèmes. Nous définissons le -blocs d'un graphique G comme une généralisation des blocs de G, Où est un sous-ensemble de l'ensemble de sommets de G; et définir le -centroïde de G comme une généralisation du centre de gravité de G. Premièrement, nous prouvons que le -centroïde de G est inclus dans un -bloc de G. Il s'agit d'une généralisation des théorèmes ci-dessus concernant le centroïde, de Jordan et Truszczynski. Deuxièmement, nous définissons le -centre de G comme une généralisation de k-centre de G et prouver quelques théorèmes concernant la localisation de -centre. En utilisant l’un des théorèmes démontrés ici, nous pouvons facilement obtenir le théorème montrant que le k-centre de chaque graphique connecté G se trouve dans un seul bloc de G. Ce théorème est une généralisation du théorème ci-dessus de Slater.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.10 pp.2009-2014
Date de publication
2000/10/25
Publicisé
ISSN en ligne
DOI
Type de manuscrit
PAPER
Catégories
Graphiques et réseaux

Auteurs

Mots-clés

Table des matières