Portal de Periódicos da CAPES

Centers to centroids in graphs

1978; Wiley; Volume: 2; Issue: 3 Linguagem: Inglês

10.1002/jgt.3190020304

1097-0118

Peter J. Slater,

Facility Location and Emergency Management

Abstract For S ⊆ V ( G ) the S ‐center and S ‐centroid of G are defined as the collection of vertices u ∈ V ( G ) that minimize e s ( u ) = max { d ( u, v ): v ∈ S } and d s ( u ) = ∑ u∈S d ( u, v ), respectively. This generalizes the standard definition of center and centroid from the special case of S = V ( G ). For 1 ⩽ k ⩽| V ( G )| and u ∈ V ( G ) let r k ( u ) = max {∑ s ∈ S d ( u, s ): S ⊆ V ( G ), | S | = k }. The k ‐centrum of G , denoted C ( G; k ), is defined to be the subset of vertices u in G for which r k ( u ) is a minimum. This also generalizes the standard definitions of center and centroid since C ( G ; 1) is the center and C ( G ; | V ( G )|) is the centroid. In this paper the structure of these sets for trees is examined. Generalizations of theorems of Jordan and Zelinka are included.