×

Steiner numbers in graphs. (English) Zbl 0707.05037

Summary: The Steiner distance d(S) of a set S of vertices in a connected graph G is the minimum size of a connected subgraph of G that contains S. The Steiner number s(G) of a connected graph G of order p is the smallest positive integer m for which there exists a set S of m vertices of G such that \(d(S)=p-1\). A smallest set S of vertices of a connected graph G of order p for which \(d(S)=p-1\) is called a Steiner spanning set of G. It is shown that every connected graph has a unique Steiner spanning set. If G is a connected graph of order p and k is an integer with \(0\leq k\leq p-1\), then the kth Steiner number \(s_ k(G)\) of G is the smallest positive integer m for which there exists a set S of m vertices of G such that \(d(S)=k\). The sequence \(s_ 0(G),s_ 1(G),...,s_{p-1}(G)\) is called the Steiner sequence of G. Steiner sequences for trees are characterized.

MSC:

05C35 Extremal problems in graph theory
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chartrand G., Wadsworth & Brooks/Cole, in: Graphs & Digraphs,, 2. ed. (1986)
[2] Chartrand, G., Oellermann, O. R., Tian, S. and Zou, H. B. Steiner distance in graphs. Submitted for publication · Zbl 0688.05040
[3] Even S., Graph Algorithms (1985)
[4] Karp R. M., Complexity of Computer Computations pp 85– (1972)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.