The Steiner ratio conjecture for six points. (English) Zbl 0739.05034

Summary: We prove the Steiner ratio conjecture for six points. We use the variational approach discussed in detail in our forthcoming paper “A variational approach to the Steiner network problem”, Ann. Oper. Res. In Section 1 we give a brief discussion of the variational technique and pose the Steiner ratio conjecture as a problem of variations. In Section 2 we give some useful general variations and discuss decomposition. In Section 3 we give a proof of the Steiner conjecture for six points.


05C05 Trees
94C15 Applications of graph theory to circuits and networks
Full Text: DOI


[1] Du, D. Z.; Hwang, F. K.; Yao, E. N., The Steiner ratio conjecture is true for five points, J. Combin. Theory Ser. A, 38, 230-240 (1985) · Zbl 0576.05015
[2] Du, D. Z.; Yao, E. Y.; Hwang, F. K., A short proof of a result of Pollak on Steiner minimal trees, J. Combin. Theory Ser. A, 32, 396-400 (1982) · Zbl 0507.05028
[3] Garey, M. R.; Graham, R. L.; Johnson, D. S., The complexity of computing Steiner minimal trees, SIAM J. Appl. Math., 32, 835-859 (1977) · Zbl 0399.05023
[4] Gilbert, E. N.; Pollak, H. O., Steiner minimal trees, SIAM J. Appl. Math., 16, 1-29 (1968) · Zbl 0159.22001
[5] Kruskal, J. B., On the shortest spanning subtree of a graph and the travelling salesman problem, (Proc. Amer. Math. Soc., 7 (1956)), 48-50 · Zbl 0070.18404
[6] Melzak, Z. A., On the problem of Steiner, Canad. Math. Bull, 4, 143-148 (1961) · Zbl 0101.13201
[7] Pollak, H. O., Some remarks on the Steiner problem, J. Combin. Theory Ser. A, 24, 278-295 (1978) · Zbl 0392.05021
[8] Prim, R. C., Shortest connection networks and some generalizations, Bell Systems Tech. J., 36, 1389-1401 (1957)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.