zbMATH — the first resource for mathematics

Optimal embeddings of odd ladders into a hypercube. (English) Zbl 1005.05016
An embedding of a graph \(G\) into (the graph of) a hypercube of dimension \(k\) is called optimal if the number of vertices of \(G\) is greater than \(2^{k-1}\). A ladder is a graph consisting of two paths of the same length \(n\) and of \(n+1\) paths, called rungs, such that the corresponding vertices of the two paths are connected by one of the rungs. Such a ladder is called odd if all its rungs are of odd size.
Continuing their own work (see [Eur. J. Comb. 18, 249-266 (1997; Zbl 0883.05041)]) and that of others (see S. Bezrukov, B. Monien, W. Unger and G. Wechsung [Discrete Appl. Math. 83, 21-29 (1998; Zbl 0906.05019)]) the authors prove that every odd ladder with rungs of sizes greater than 6 has an optimal embedding into a hypercube. An example of an odd ladder with ten rungs of sizes 3 and 5 is given, found by a computer program, which does not have an optimal embedding into a hypercube. It remains open whether each odd ladder with rungs of sizes at least 5 has an optimal embedding into a hypercube. All proofs depend on sophisticated investigations of so-called dense sets in hypercubes.

05C10 Planar graphs; geometric and topological aspects of graph theory
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] S. Bezrukov, B. Monien, W. Unger, G. Wechsung, Embedding ladders and caterpillars into the hypercube, Preprint, 1996. · Zbl 0906.05019
[2] S. Bezrukov, B. Monien, W. Unger, G. Wechsung, Embedding caterpillars into the hypercube, Discr. Appl. Math. 83 (1998) 21-29. · Zbl 0906.05019
[3] Caha, R.; Koubek, V., Spanning regular caterpillars, European J. combin., 18, 249-266, (1997) · Zbl 0883.05041
[4] Dvořák, T.; Havel, I.; Laborde, J-M.; Mollard, M., Spanning caterpillars of a hypercube, J. graph theory, 24, 9-19, (1997) · Zbl 0865.05034
[5] F. Harary, Recent results and unsolved problems on hypercube theory, in: Graph Theory, Combinatorics and Applications, Vol. 2, Wiley Insterscience, New York, 1991, pp. 621-632. · Zbl 0840.05092
[6] Havel, I.; Liebel, P., One-legged caterpillars span hypercubes, J. graph theory, 10, 69-77, (1986) · Zbl 0589.05031
[7] Leighton, F.T., Introduction to parallel algorithms and architectures: arrays, trees, hypercubes, (1992), Morgan Kaufmann San Mateo, CA · Zbl 0743.68007
[8] B. Monien, I.H. Sudborough, Comparing Interconnection Networks, Proceedings of the MFCS’88, Lecture Notes in Computer Science, Vol. 324, Springer, Berlin, 1988, pp. 138-153.
[9] Nebeský, L., On cubes and dichotomic trees, Časopis Pěst. matem., 99, 164-167, (1974) · Zbl 0277.05101
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.