Optimal embeddings of odd ladders into a hypercube
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.NEWLINENEWLINENEWLINEContinuing their own work (see [Eur. J. Comb. 18, 249-266 (1997; Zbl 0883.05041)]) and that of others (see \textit{S. Bezrukov}, \textit{B. Monien}, \textit{W. Unger} and \textit{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.
- Optimal embeddings of generalized ladders into hypercubes
- Embedding ladders and caterpillars into the hypercube
- Embedding of Grids into Optimal Hypercubes
- An optimal embedding of cycles into incomplete hypercubes
- The embedding of graphs in hypercubes and cubic lattices
- A probably optimal embedding of hyper-rings in hypercubes
- Embedding multidimensional grids into optimal hypercubes
- Optimal embedding of hypercube into cylinder
- Optimal subcube embeddability in hypercubes with additional dimensions
- Optimal embedding of locally twisted cubes into grids
- Embedding ladders and caterpillars into the hypercube
- scientific article; zbMATH DE number 52113 (Why is no real title available?)
- scientific article; zbMATH DE number 867627 (Why is no real title available?)
- On cubes and dichotomic trees
- One-legged caterpillars span hypercubes
- Spanning caterpillars of a hypercube
- Spanning regular caterpillars in hypercubes
- Embedding ladders and caterpillars into the hypercube
- Spanning multi-paths in hypercubes
- Optimal embedding of hypercube into cylinder
- The optimal rubbling number of ladders, prisms and Möbius-ladders
- Embedding a subclass of trees into hypercubes
- Optimal embeddings of generalized ladders into hypercubes
- Dense sets and embedding binary trees into hypercubes
This page was built for publication: Optimal embeddings of odd ladders into a hypercube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5957299)
