zbMATH — the first resource for mathematics

Embedding ladders and caterpillars into the hypercube. (English) Zbl 0906.05019
Summary: We present an embedding of generalized ladders as subgraphs into the hypercube. Through an embedding of caterpillars into ladders, we obtain an embedding of caterpillars into the hypercube. In this way we get almost all known results concerning the embedding of caterpillars into the hypercube. In addition we construct an embedding for some new types of caterpillars. Our results support the conjecture of I. Havel in [Čas. Pěstování Mat. 109, 135-152 (1984; Zbl 0544.05057)].

05C10 Planar graphs; geometric and topological aspects of graph theory
05C05 Trees
Zbl 0544.05057
Full Text: DOI Link
[1] S.L. Bezrukov, B. Monien, W. Unger, G. Wechsung, Dense subsets and their use in embedding problems, Technical Report, University of Paderborn, to appear. · Zbl 0906.05019
[2] Bhatt, S.N.; Chung, F.R.K.; Leighton, F.T.; Rosenberg, A.L., Efficient embedding of trees in hypercube, SIAM J. comput., 21, 1, 151-162, (1990)
[3] Dvor̆ák, T.; Havel, I.; Laborde, J.-M.; Mollard, M., Spanning caterpillars of the hypercube, () · Zbl 0865.05034
[4] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco · Zbl 0411.68039
[5] Haralambides, J.; Makedon, R.; Monien, B., Bandwidth minimization: an approximation algorithm for caterpillars, Math. systems theory, 24, 169-177, (1991) · Zbl 0767.68081
[6] Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064
[7] Harary, F.; Lewinter, M., Spanning subgraphs of a hypercube VI: survey and unsolved problems, (), 633-637 · Zbl 0840.05091
[8] Harary, F.; Lewinter, M.; Widulski, W., On two-legged caterpillars which span hypercubes, (), 103-108 · Zbl 0692.05023
[9] Harary, F.; Schwenk, A.J., The number of caterpillars, Discrete math., 6, 359-365, (1973) · Zbl 0266.05102
[10] Havel, I., On Hamiltonian circles and spanning trees of hypercube graphs, C̆as. Pést. mat., 109, 135-152, (1984) · Zbl 0544.05057
[11] Havel, I., On certain trees in hypercube, (), 353-358 · Zbl 0743.05016
[12] I. Havel, J.-M. Laborde, P. Liebl, Caterpillar-like trees spanning hypercubes, C̆as. Pést. Mat., to appear.
[13] Havel, I.; Liebl, P., One-legged caterpillars span hypercubes, J. graph theory, 10, 69-78, (1986) · Zbl 0589.05031
[14] Lifschitz, A.; Redstone, A., A determination of the number of caterpillars, Southeast Asian bull. math., 9, 1, 50-52, (1985) · Zbl 0586.05023
[15] Monien, B., The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete, SIAM J. algebraic discrete meth., 7, 4, 505-512, (1986) · Zbl 0624.68059
[16] Monien, B.; Sudborough, I.H., Simulating binary trees on hypercubes, (), 170-180
[17] Monien, B.; Sudborough, I.H., Embedding one interconnection network in another, Computing, 7, 257-282, (1990), (Suppl) · Zbl 0699.68017
[18] Wagner, A.S., Embedding trees into the hypercube, () · Zbl 0800.68150
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.