Strong isometric dimension, biclique coverings, and Sperner's Theorem

Nice constructive proof using Sperner's Theorem.

Abstract

The strong isometric dimension of a graph G is the least number k such that G isometrically embeds into the strong product of k paths. Using Sperner's Theorem, the strong isometric dimension of the Hamming graphs K₂ × K_n is determined.

Status

Published.

D. Fronček, J. Jerebic, S. Klavžar, P. Kovář, Strong isometric dimension, biclique coverings, and Sperner's Theorem, Combinatorics Probability and Computing, 16, (2007), p. 271-275.

---

Petr<dot>Kovar<at>vsb<dot>cz phone ++420 / 597 325 972

Last update: 29.12.2011