Optimal embeddings of generalized ladders into hypercubes (Q5936018): Difference between revisions

A hypercube of dimension \(n\) is a graph whose vertex set consists of all binary vectors of length \(n\), two vertices being adjacent iff the corresponding vectors differ in exactly one coordinate. A graph \(G\) has an optimal embedding into a hypercube if \(G\) is isomorphic to a subgraph of the hypercube of dimension \(\lceil\log_2|V(G)|\rceil\). Any hypercube is balanced, i.e. a bipartite graph with equal-sized classes of bipartition. Motivated by a conjecture of \textit{I. Havel} [Čas. Pěst. Mat. 109, 135-152 (1984; Zbl 0544.05057)] saying that every balanced tree of maximum degree three has an optimal embedding into a hypercube, \textit{S. Bezrukov} et al. [Discrete Appl. Math. 83, No. 1-3, 21-29 (1998; Zbl 0906.05019)] showed that an optimal embedding exists for another class of balanced graphs, called ladders with even rungs. This paper generalizes their result. The authors introduce a generalized ladder as a graph \(G\) consisting of two disjoint paths \(P_0=(x_0,x_1,\dots,x_n)\), \(P_1=(y_0,y_1,\dots,y_m)\) and \(p\) pairwise disjoint paths \(R_i=(z_{i,0},z_{i,1},\dots,z_{i,l_i})\) for \(i\in\{0,1,\dots,p-1\}\) such that each \(R_i\) has exactly one vertex \(z_{i,0}=x_{j_i}\) (\(z_{i,l_i}=y_{k_i}\)) in common with \(P_0\) (\(P_1\)) for some \(j_i\in\{0,1,\dots,n\}\) (\(k_i\in\{0,1,\dots,m\}\)) and moreover, \(j_i<j_{i'}\) (\(k_i<k_{i'}\)) for all \(i<i'\). \(G\) has even (odd) rungs whenever all \(l_i\)'s are odd (even). The main results of the paper are optimal embeddings into a hypercube for two classes of generalized ladders: balanced generalized ladders with even rungs, and so-called pretty generalized ladders, which form a proper subclass of balanced generalized ladders with odd rungs. The proofs are based on sophisticated inductive constructions which generalize methods of Bezrukov et al.