Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-27T15:21:53.119Z Has data issue: false hasContentIssue false
  • English
  • Français

On Oriented Embedding of the Binary Tree into the Hypercube

Published online by Cambridge University Press:  12 September 2008

Sergej L. Bezrukov
Sergej L. Bezrukov
Affiliation:
Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2–6, D-14195 Berlin
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the oriented binary tree and the oriented hypercube. The tree edges are oriented from the root to the leaves, while the orientation of the cube edges is induced by the direction from 0 to 1 in the coordinatewise form. The problem is to embed such a tree with l levels into the oriented n-cube as an oriented subgraph, for minimal possible n. A new approach to such problems is presented, which improves the known upper bound n/l ≤ 3/2 given by Havel [1] to n/l ≤ 4/3 + o(1) as l → ∞.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 3 , Issue 1 , March 1994 , pp. 27 - 38
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Havel, I. (1982) Embedding the directed dichotomic tree into the n-cube. Rostock. Math. Kolloq. 21 39–45.Google Scholar
[2]Havel, I. and Liebl, P. (1972) O vnořeni dichotomického stromu do crychle (Czech, English summary). Čas. Pěst. Mat. 97 201–205.CrossRefGoogle Scholar
[3]Havel, I. and Liebl, P. (1973) Embedding the polythomic tree into the n-cube. Čas. Pěst. Mat. 98 307–314.CrossRefGoogle Scholar
[4]Nebeský, L. (1974) On cubes and dichotomic trees. Čas. Pěst. Mat. 99 164–167.CrossRefGoogle Scholar
[5]Ollé, F. (1972) M. Sci. Thesis, Math. Inst., Prague.Google Scholar
[6]Wagner, A. S. (1987) Embedding trees in the hypercube, Technical Report 204/87, Dept. of Computer Science, University of Toronto.Google Scholar