Embedding complete trees into the hypercube |
| |
Authors: | Sergei L Bezrukov |
| |
Institution: | Department of Mathematics and Computer Science, University of Wisconsin – Superior, Superior, WI 54880-4500, USA |
| |
Abstract: | We consider embeddings of the complete t-ary trees of depth k (denotation Tk,t) as subgraphs into the hypercube of minimum dimension n. This n, denoted by dim(Tk,t), is known if max{k,t}2. First, we study the next open cases t=3 and k=3. We improve the known upper bound dim(Tk,3)2k+1 up to limk→∞dim(Tk,3)/k5/3 and show limt→∞dim(T3,t)/t=227/120. As a co-result, we present an exact formula for the dimension of arbitrary trees of depth 2, as a function of their vertex degrees. These results and new techniques provide an improvement of the known upper bound for dim(Tk,t) for arbitrary k and t. |
| |
Keywords: | Embedding Dilation Complete tree Hypercube |
本文献已被 ScienceDirect 等数据库收录! |
|