Paper Info
Title
Steiner intervals in graphs
Abstract
Let G be a graph and u , v two vertices of G . Then the interval from u to v consists of all those vertices that lie on some shortest u — v path. Let S be a set of vertices in a connected graph G . Then the Steiner distance d G ( 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 G ( 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 k ( S ) is the intersection of all Steiner intervals of all k -subsets of S . It is shown that if S = { u 1 , u 2 , …, u n } is a set of n ⩾ 2 vertices of a graph G and if the 2-intersection interval of S is nonempty and xϵI 2 ( S ), then d(S) = ∑ n i = 1 = 1 d(u i , x). It is observed that the only graphs for which the 2-intersection intervals of all n -sets, n ⩾ 4, are nonempty are stars. Moreover, for every n ⩾ 4, those graphs with the property that the 3-intersection interval of every n -set is nonempty are completely characterized. In general, if n = 2 k , those graphs G for which I k ( S ) is nonempty for every n -set S of G are characterized.
Year
DOI
Venue
1998
10.1016/S0166-218X(97)00084-X
Discrete Applied Mathematics
Keywords
Field
DocType
median graph,steiner tree,steiner interval,graph theory,connected graph,shortest path,tree graph
Graph theory,Graph,Discrete mathematics,Combinatorics,Tree (graph theory),Shortest path problem,Vertex (geometry),Steiner tree problem,Connectivity,Median graph,Mathematics
Journal
Volume
Issue
ISSN
81
1-3
Discrete Applied Mathematics
Citations 
PageRank 
References 
12
0.97
13
Authors
3
Name
Order
Citations
PageRank
Ewa Kubicka1669.61
Grzegorz Kubicki29515.16
Ortrud R. Oellermann342461.05