✦ LIBER ✦

Steiner centers in graphs

✍ Scribed by Ortrud R. Oellermann; Songlin Tian

Publisher: John Wiley and Sons
Year: 1990
Tongue: English
Weight: 515 KB
Volume: 14
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190140510

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The Steiner distance of a set S of vertices in a connected graph G is the minimum size among all connected subgraphs of G containing S. For n ≥ 2, the n‐eccentricity e~n~(ν) of a vertex ν of a graph G is the maximum Steiner distance among all sets S of n vertices of G that contains ν. The n‐diameter of G is the maximum n‐eccentricity among the vertices of G while the n‐radius of G is the minimum n‐eccentricity. The n‐center of G is the subgraph induced by those vertices of G having minimum n‐eccentricity. It is shown that every graph is the n‐center of some graph. Several results on the n‐center of a tree are established. In particular, it is shown that the n‐center of a tree is a tree and those trees that are n‐centers of trees are characterized.

📜 SIMILAR VOLUMES

On Steiner centers and Steiner medians o

On Steiner centers and Steiner medians of graphs

✍ Oellermann, Ortrud R. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB

Let G be connected graph and S a set of vertices of G. Then a Steiner tree for S is a connected subgraph of G of smallest size (number of edges) that contains S. The size of such a subgraph is called the Steiner distance for S and is denoted by d(S). For a vertex v of G, and integer n, 2 Յ n Յ ͉V(G)

From steiner centers to steiner medians

✍ Ortrud R. Oellermann 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 457 KB

## Abstract The Steiner distance of set __S__ of vertices in a connected graph __G__ is the minimum number of edges in a connected subgraph of __G__ containing __S__. For __n__ ≥ 2, the Steiner __n__‐eccentricity __e~n~__(__v__) of a vertex __v__ of a graph __G__ is the maximum Steiner distance amo

Steiner intervals in graphs

✍ Ewa Kubicka; Grzegorz Kubicki; Ortrud R. Oellermann 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 664 KB

Let G be a graph and U, L' two vertices of G. Then the interval from K to 2' consists of all those vertices that lie on some shortest u -1; path. Let S be a set of vertices in a connected graph G. Then the Steiner distance d,(S) of S in G is the smallest number of edges in a connected subgraph of G

The steiner problem in graphs

✍ S. E. Dreyfus; R. A. Wagner 📂 Article 📅 1971 🏛 John Wiley and Sons 🌐 English ⚖ 567 KB

Steiner distance stable graphs

✍ Wayne Goddard; Ortrud R. Oellermann; Henda C. Swart 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 673 KB

Let G be a connected graph and S a nonempty set of vertices of G. Then the Steiner distance d,(S) of S is the smallest number of edges in a connected subgraph of G that contains S. Let k, I, s and m be nonnegative integers with m > s > 2 and k and I not both 0. Then a connected graph G is said to be

Centers to centroids in graphs

✍ Peter J. Slater 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 527 KB

For S E V(G) the S-center and S-centroid of G are defined as the collection of vertices u E V(G) that minimize eJu) = max {d (u, v ) : V E S} and & ( u ) =IveS d (u, v), respectively. This generalizes the standard definition of center and centroid from the.special case of S = V(G). For is defined t