Premium
Center, median, and centroid subgraphs
Author(s) -
Smart Christian,
Slater Peter J.
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199912)34:4<303::aid-net10>3.0.co;2-#
Subject(s) - centroid , center (category theory) , median , computer science , combinatorics , mathematics , artificial intelligence , geometry , chemistry , crystallography
The median and centroid of an arbitrary graph G are two different generalizations of the branch weight centroid of a tree. As such, they are closely related, but they can actually be disjoint. On the one hand, they are, for example, always contained in the same block of any connected graph G . However, they can be arbitrarily far apart. Specifically, given any three graphs H , J , and K , and a positive integer k ≥ 4, there exists a graph G with center, median, and centroid subgraphs isomorphic to H , J , and K , respectively, and the distance between any two of these subgraphs is at least k . © 1999 John Wiley & Sons, Inc. Networks 34: 303–311, 1999