Steiner intervals in graphs (Q1382264): Difference between revisions

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.