Minimal Steiner trees for rectangular arrays of lattice points
type: Item
instance of: scholarly article
title: Minimal Steiner trees for rectangular arrays of lattice points
zbMATH Open document ID: 0883.05038
published in: Journal of Combinatorial Theory. Series A
publication date: 1998-02-05T00:00:00Z
review text: 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 \textit{F. Chung}, \textit{M. Gardner} and \textit{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.
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1051477
zbMATH Keywords: minimal Steiner trees
zbMATH Keywords: full components of a Steiner tree
zbMATH Keywords: lattice points
author: M. Brazil
author: J. Hyam Rubinstein
author: D. A. Thomas
author: J. F. Weng
author: Nicholas Wormald
reviewed by: Johann Linhart
MaRDI profile type: Publication
full work available at URL: jcta.1996.2751
OpenAlex ID: W2063178228
cites work: Minimal Steiner trees for \(2^ k \times 2^ k\) square lattices
cites work: Full minimal Steiner trees on lattice sets
cites work: Steiner Trees on a Checkerboard
cites work: Steiner Trees for Ladders
cites work: The Steiner tree problem
DOI: 10.1006/JCTA.1996.2751
description: scientific article; zbMATH DE number 1051477