×

Steiner intervals in graphs. (English) Zbl 0898.05044

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.

MSC:

05C38 Paths and cycles
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Avann, S. P., Metric ternary distributive semi-lattices, (Proc. Amer. Math. Soc., 12 (1961)), 407-414 · Zbl 0099.02201
[2] Bandelt, H. J., Centroids and median of finite metric spaces, J. Graph Theory, 16, 305-317 (1992) · Zbl 0849.05027
[3] Bandelt, H. J.; Barthelemy, J. P., Median in median graphs, Discrete Appl. Math., 8, 131-142 (1984) · Zbl 0536.05057
[4] Barbut, M., Médiane, distributivité,éloignements, Math et Sci. Hum., 70, 5-31 (1980) · Zbl 0439.06007
[5] Barthelemy, J. P.; Janowitz, M. F., A formal theory of consensus, SIAM J. Discrete Math., 4, 305-322 (1991) · Zbl 0734.90008
[6] Barthelemy, J. P.; McMorris, F. R., The median procedure for \(n\)-trees, J. Classification, 3, 329-334 (1986) · Zbl 0617.62066
[7] Barthelemy, J. P.; Monjardet, B., The median procedure in cluster analysis and social choice theory, Math. Social Sci., 1, 235-268 (1981) · Zbl 0486.62057
[8] Chartrand, G.; Oellermann, O. R., Applied and Algorithmic Graph Theory (1993), McGraw-Hill: McGraw-Hill New York
[9] P. Dankelmann, O.R. Oellermann, H.C. Swart, Bounds on the average distance of graphs with specified properties, Discrete Applied Math., to appear.; P. Dankelmann, O.R. Oellermann, H.C. Swart, Bounds on the average distance of graphs with specified properties, Discrete Applied Math., to appear. · Zbl 0884.05040
[10] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to NP- completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[11] Goldman, A. J., Optimal center location in simple networks, Transportation Sci., 5, 212-221 (1971)
[12] Györi, E., On division of graphs to connected graphs, Combinatorics, ((1978), North-Holland: North-Holland New York), 485-494
[13] Hansen, P.; Thisse, J. F., Outcomes of voting and planning: Condorcet. Weber and Rawls locations, J. Public Econom, 16, 1-15 (1981)
[14] Jha, P. K.; Slutzki, G., Convex-expansions algorithms for recognition isometric embedding of median graphs, Ars Combin., 34, 75-92 (1992) · Zbl 0770.05043
[15] Leclerc, B., Medians and majorities in semimodular lattices, SIAM J. Discrete Math., 3, 266-276 (1990) · Zbl 0698.06003
[16] Leclerc, B., Lattices, valuations, medians and majorities, Discrete Math., 111, 345-356 (1993) · Zbl 0785.06006
[17] Leclerc, B., Medians for weight metrics in covering graphs of semilattices, Discrete Appl. Math., 49, 281-297 (1994) · Zbl 0794.06002
[18] Lovász, L., A homology theory for spanning trees of a graph, Acta Math. Acad. Sci. Hungar., 30, 241-251 (1977) · Zbl 0403.05040
[19] F.R. McMorris, H.M. Mulder, F.S. Roberts, The median procedure on median graphs. Discrete Applied Math., to appear.; F.R. McMorris, H.M. Mulder, F.S. Roberts, The median procedure on median graphs. Discrete Applied Math., to appear. · Zbl 0906.05023
[20] McMorris, F. R.; Powers, R. C., The median procedure in a formal theory of consensus, SIAM J. Discrete Math., 8, 507-516 (1995) · Zbl 0843.90008
[21] Mitchell, S. L., Another characterization of the centroid of a tree, Discrete Math., 24, 277-280 (1978) · Zbl 0402.05019
[22] Mulder, H. M., The Interval Function of a graph (1980), Mathematical Centre Tracts 132: Mathematical Centre Tracts 132 Amsterdam · Zbl 0446.05039
[23] Mulder, H. M., The structure of median graphs, Discrete Math., 24, 197-204 (1978) · Zbl 0394.05038
[24] Mulder, H. M.; Schrijver, A., Median graphs and Helly hypergraphs, Discrete Math., 25, 41-50 (1979) · Zbl 0395.05058
[25] Nebésky, L., Median graphs, Comment. Math. Univ. Carolinae, 12, 317-325 (1971) · Zbl 0215.34001
[26] Slater, P. J., Medians of arbitrary graphs, J. Graph Theory, 4, 389-392 (1980) · Zbl 0446.05029
[27] Vohra, R. V., An axiomatic characterization of some locations in trees, European J. Oper. Res., 90, 78-84 (1996) · Zbl 0914.90182
[28] Zelinka, B., Medians and periferian of trees, Arch. Math. (Brno), 67-95 (1968) · Zbl 0206.26105
[29] Zelinka, B., A modification of the median of a tree, Math. Bohemica, 118, 195-200 (1993) · Zbl 0778.05030
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.