Optimal embeddings of odd ladders into a hypercube Original Research Article

An embedding of a graph G into a hypercube of dimension k is called optimal if the number of vertices of G is greater than 2k−1. A ladder is a special graph in which two paths of the same length are connected in such a way that each vertex of the first one is connected by a path – called a rung – to its corresponding vertex in the second one. We construct an optimal embedding for every ladder with rungs of odd sizes greater than 6 into a dense set of a hypercube.