Optimal embeddings of generalized ladders into hypercubes
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. NEWLINENEWLINENEWLINEThe 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.
- Optimal embeddings of odd ladders into a hypercube
- Balanced caterpillars of maximum degree 3 and with hairs of arbitrary length are subgraphs of their optimal hypercube
- On embedding subclasses of height-balanced trees in hypercubes
- A note on the cubical dimension of new classes of binary trees.
- One-legged caterpillars span hypercubes
- Embedding complete binary trees into hypercubes
- Embedding complete ternary trees into hypercubes
- A characterization of totally balanced hypergraphs
- Embedding ladders and caterpillars into the hypercube
- Embedding certain height-balanced trees and complete p^m-ary trees into hypercubes
- Exact wirelength of hypercubes on a grid
- Embedding ladders and caterpillars into the hypercube
- Embedding hypercubes and folded hypercubes onto Cartesian product of certain trees
- Wirelength of hypercubes into certain trees
- A linear time algorithm for embedding hypercube into cylinder and torus
- Spanning multi-paths in hypercubes
- Embedding of hypercubes into sibling trees
- scientific article; zbMATH DE number 434916 (Why is no real title available?)
- Embeddings of circulant networks
- Embedding m-quasistars into n-cubes
- Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength
- Embedding of hypercubes into necklace, windmill and snake graphs
- Bothway embedding of circulant network into grid
- On the balanced domination of graphs
- Embedding a subclass of trees into hypercubes
- Optimal embeddings of odd ladders into a hypercube
- Exact Wirelength of Embedding 3-Ary n-Cubes into Certain Cylinders and Trees
- Embedding Wheel - like Networks
- Minimum average congestion of enhanced and augmented hypercubes into complete binary trees
- Optimal subcube embeddability in hypercubes with additional dimensions
- Embedding crossed cube into diverse product graphs and tree-derived architectures
This page was built for publication: Optimal embeddings of generalized ladders into hypercubes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5936018)
