Optimal embeddings of odd ladders into a hypercube (Q5957299)
From MaRDI portal
scientific article; zbMATH DE number 1716681
Language | Label | Description | Also known as |
---|---|---|---|
English | Optimal embeddings of odd ladders into a hypercube |
scientific article; zbMATH DE number 1716681 |
Statements
Optimal embeddings of odd ladders into a hypercube (English)
0 references
3 July 2002
0 references
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 \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.
0 references