Steiner intervals in graphs (Q1382264): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Ewa M. Kubicka / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Grzegorz M. Kubicki / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Bohdan Zelinka / rank | |||
Normal rank |
Revision as of 12:01, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Steiner intervals in graphs |
scientific article |
Statements
Steiner intervals in graphs (English)
0 references
25 March 1998
0 references
If \(S\) is a subset of the vertex set of a connected graph \(G\), then the Steiner distance \(d(S)\) of \(S\) is the minimum number of edges of a connected subgraph of \(G\) that contains \(S\); this subgraph is always a tree and is called a Steiner tree for \(S\). The Steiner interval \(I(S)\) of \(S\) is the set of all vertices of \(G\) which lie in a Steiner tree for \(S\). If \(S\) has \(n\) elements and \(k\leq n\), then the \(k\)-intersection interval \(I_k(S)\) is the intersection of all Steiner intervals of subsets of \(S\) having \(k\) vertices. The question when \(I_k(S)\) is non-empty is studied and some theorems concerning it are proved. The most general theorem is the following: Let \(G\) be a graph of order \(p\geq n\) and suppose \(n\geq 2k\). Then \(I_k(S)\) is non-empty for every \(n\)-set \(S\) of vertices of \(G\) if and only if \(G\) has a cut vertex \(v\) such that every component of \(G-v\) has at most \(k-1\) vertices.
0 references
path
0 references
Steiner distance
0 references
Steiner tree
0 references
Steiner interval
0 references