×
Brazil, M.; Rubinstein, J. H.; Thomas, D. A.; Weng, J. F.; Wormald, N. C.

Minimal Steiner trees for rectangular arrays of lattice points. (English) Zbl 0883.05038

J. Comb. Theory, Ser. A 79, No. 2, 181-208 (1997).
By distinction of several cases, the authors are able to construct a minimal Steiner tree for an arbitrary rectangular array of integer lattice points in the plane. For \(n\times n\)-arrays, this proves a conjecture by F. Chung, M. Gardner and R. Graham [Math. Mag. 62, No. 2, 83-96 (1989; Zbl 0681.05018)] with the exception of the case \(n\equiv 0\bmod 6\), \(n>6\), where the authors were able to improve the conjecture. The proof rests on a theorem of another paper by the same authors [J. Comb. Theory, Ser. A 78, No. 1, 51-91 (1997; Zbl 0874.05018)], which characterizes the full components of a minimal Steiner tree for somewhat more general lattice sets. For non-square rectangular arrays, the proof is rather involved, but many drawings help to understand the constructions.
Reviewer: J.Linhart (Salzburg)

Cited in 6 Documents

MSC:

05C05 Trees

Keywords:

minimal Steiner trees; full components of a Steiner tree; lattice points

Citations:

Zbl 0681.05018; Zbl 0874.05018
Cite Review PDF
Full Text: DOI

References:

[1] Brazil, M.; Cole, T.; Rubinstein, J. H.; Thomas, D. A.; Weng, J. F.; Wormald, N. C., Minimal Steiner trees for \(2^k\)×\(2^k\) Square Lattices, J. Combin. Theory, Series A, 73, 91-110 (1996) · Zbl 0844.05036
[2] M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, N. C. Wormald, Full minimal Steiner trees on lattice sets, J. Combin. Theory, Series A; M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, N. C. Wormald, Full minimal Steiner trees on lattice sets, J. Combin. Theory, Series A · Zbl 0874.05018
[3] Chung, F. R.K.; Gardner, M.; Graham, R. L., Steiner trees on a checkerboard, Math. Magazine, 62, 83-96 (1989) · Zbl 0681.05018
[4] Chung, F. R.K.; Graham, R. L., Steiner trees for ladders, Ann. Disc. Math., 2, 173-200 (1978) · Zbl 0384.05030
[5] Hwang, F. K.; Richards, D. S.; Winter, P., The Steiner Tree Problem. The Steiner Tree Problem, Annals of Discrete Mathematics, 53 (1992), North-Holland: North-Holland Amsterdam · Zbl 0774.05001
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.