Embedding complete trees into the hypercube
For given tree \(T\), the dimension of \(T\) (denoted by \(\text{dim}(T)\)) is the minimum \(n\) such that \(T\) is a subgraph of the \(n\)-dimensional hypercube. In the paper, the dimension of complete \(t\)-ary trees \(T^{k,t}\) of depth \(k\) is considered. It is known that \(\frac{kt}{e} \leq \dim(T^{k,t}) \leq \frac{(k+1)t}{2}+k-1\) [see \textit{F. Ollé}, M. Sci. Thesis, Math. Inst. Prague (1972)], \(\dim(T^{k,2})=k+2\), \(k \geq 2\) and \(\dim(T^{2,t})=\lceil \frac{3t+1}{2}\rceil\), \(t \geq 1\) [see \textit{I. Havel} and \textit{P. Liebl}, Čas. Pěst. Mat. 97, 201-205 (1972; Zbl 0229.05109) and Čas. Pěst. Mat. 98, 307-314 (1973; Zbl 0274.05101)]. For the next open cases \(k=3\) and \(t=3\), it is known that \(\dim(T^{3,t}) \leq 2t+2\), \(\dim(T^{k,3}) \leq 2k +1\) (H.-D. O. F. Gronau and J.-M. Laborde (1994)). The author improves the leading coefficients 2 in these upper bounds, showing that NEWLINE\[NEWLINE\lim_{k \to \infty}\frac{\dim(T^{k,3})}{k} \leq \frac{5}{3}\quad\text{and}\quad\lim_{t \to \infty}\frac {\dim(T^{3,t})}{t} = \frac{227}{120}.NEWLINE\]NEWLINE Also, the general upper bound is improved asymptotically by showing that NEWLINE\[NEWLINE\lim_{k,t \to \infty} \frac{\dim(T^{k,t})}{kt} \leq \frac{307}{640}.NEWLINE\]NEWLINE As a co-result, an exact formula for the dimension of arbitrary trees of depth 2 as a function of their vertex degrees is presented.
- Embedding the dichotomic tree into the n-cube
- Embedding the polytomic tree into the n-cube
- scientific article; zbMATH DE number 3821764 (Why is no real title available?)
- scientific article; zbMATH DE number 3041944 (Why is no real title available?)
- On cubes and dichotomic trees
- On Oriented Embedding of the Binary Tree into the Hypercube
- Parallel concepts in graph theory
- Transversal theory. An account of some aspects of combinatorial mathematics
- Exact wirelength of hypercubes on a grid
- Embedding meshes of trees into deBruijn graphs
- Embedding hypercubes and folded hypercubes onto Cartesian product of certain trees
- Wirelength of hypercubes into certain trees
- Spanning multi-paths in hypercubes
- Embedding of hypercubes into sibling trees
- Embeddings and other mappings of rooted trees into complete trees
- Embedding of the folded hypercubes into tori
- Embedding circulant networks into butterfly and benes networks
- Complete k-ary trees and Hamming graphs
- Embeddings Between Hypercubes and Hypertrees
- Improved bound for dilation of an embedding onto circulant networks
- scientific article; zbMATH DE number 3859148 (Why is no real title available?)
- Embedding of Generalized Wheels into Arbitrary Trees
- Embeddings of circulant networks
- Embedding complete ternary trees into hypercubes
- Embedding certain height-balanced trees and complete p^m-ary trees into hypercubes
- Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength
- Embedding of hypercubes into necklace, windmill and snake graphs
- Embedding binary trees into crossed cubes
- Embedding of special classes of circulant networks, hypercubes and generalized Petersen graphs
- scientific article; zbMATH DE number 7250384 (Why is no real title available?)
- A note on the cubical dimension of new classes of binary trees.
- Embedding a subclass of trees into hypercubes
- Exact Wirelength of Embedding 3-Ary n-Cubes into Certain Cylinders and Trees
- On linear layout of bicube and construction of optimal incomplete bicube
- Panconnectivity and edge-pancyclicity of k-ary n-cubes with faulty elements
- Compact embedding of binary trees into hypercubes
- Optimal layout of embedding onto folded hypercubes
- Embedding crossed cube into diverse product graphs and tree-derived architectures
This page was built for publication: Embedding complete trees into the hypercube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5936455)
