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

Rubinstein, J. H.; Thomas, D. A.

J. Comb. Theory, Ser. A 58, No. 1, 54-77 (1991).

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.

MSC:

05C05	Trees
94C15	Applications of graph theory to circuits and networks

Keywords:

Steiner ratio conjecture; variational technique; decomposition

References:

[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)