✦ LIBER ✦

Steiner intervals in graphs

✍ Scribed by Ewa Kubicka; Grzegorz Kubicki; Ortrud R. Oellermann

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 664 KB
Volume: 81
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(97)00084-x

No coin nor oath required. For personal study only.

✦ Synopsis

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 that contains S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval I,(S) of S consists of all those vertices that lie on some Steiner tree for S. Let S be an n-set of vertices of G and suppose that k < n. Then the k-intersection interval of S. denoted by I,(S) is the intersection of all Steiner intervals of all k-subsets of S. It is shown that if s = ;a,, u2, . ..) u,j \ is a set of n 3 2 vertices of a graph G and if the 2-intersection interval of S is nonempty and x~l,(S), then d(S) = C:'= 1 d(u,,x). It is observed that the only graphs for which the ?-intersection intervals of all n-sets, n > 4, are nonempty are stars. Moreover. for every II > 4, those graphs with the property that the 3-intersection interval of every n-set is nonempty are completely characterized.

In general. if n = 2k, those graphs G for which I,(S) is nonempty for every n-set S of G are characterized.

📜 SIMILAR VOLUMES

Steiner centers in graphs

✍ Ortrud R. Oellermann; Songlin Tian 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 515 KB

## 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__ o

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

Open-interval graphs versus closed-inter

Open-interval graphs versus closed-interval graphs

✍ P. Frankl; H. Maehara 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 218 KB

A graph G = (V, E) is said to be represented by a family F of nonempty sets if there is a bijection f:V--\*F such that uv ~E if and only iff(u)Nf(v)q=~. It is proved that if G is a countable graph then G can be represented by open intervals on the real line if and only if G can be represented by clo

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)

Interval graphs and interval orders

✍ Peter C. Fishburn 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 949 KB

This paper explores the intimate connection between finite interval graphs and interval orders. Special attention is given to the family of interval orders that agree with, or provide representations of, an interval graph. Two characterizations (one by P. Hanlon) of interval graphs with essentially