Minimal Steiner trees for \(2^ k \times 2^ k\) square lattices. (English) Zbl 0844.05036

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

J. Comb. Theory, Ser. A 73, No. 1, 91-110 (1996).

The authors prove a conjecture of Chung, Graham, and Gardner, giving the form of the minimal Steiner trees for the set of points comprising the vertices of a \(2^k\times 2^k\) square lattice. The basic building block of these trees is the minimal Steiner tree of the vertices of a (unit) square.

Reviewer: J.Linhart (Salzburg)

MSC:

05C05	Trees
05C35	Extremal problems in graph theory

Keywords:

minimal Steiner trees; square lattice