×

zbMATH — the first resource for mathematics

Two new classes of trees embeddable into hypercubes. (English) Zbl 1114.05023
Summary: The problem of embedding graphs into other graphs is much studied in the graph theory. In fact, much effort has been devoted to determining the conditions under which a graph \(G\) is a subgraph of a graph \(H\), having a particular structure. An important class to study is the set of graphs which are embeddable into a hypercube. This importance results from the remarkable properties of the hypercube and its use in several domains, such as: the coding theory, transfer of information, multicriteria rule, interconnection networks ...
In this paper we are interested in defining two new classes of embedding trees into the hypercube for which the dimension is given.

MSC:
05C05 Trees
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML
References:
[1] M. Kobeissi , Plongement de graphes dans l’Hypercube . Thèse de Doctorat d’état en informatique. Université Joseph Fourier Grenoble 1 ( 2001 ).
[2] F. Harary , M. Lewinter and W. Widulski , On two legged caterpillars which span hypercubes . Cong. Numer. ( 1988 ) 103 - 108 . Zbl 0692.05023 · Zbl 0692.05023
[3] I. Havel , Embedding certain trees into hypercube , in Recent Advances in graph theory. Academia, Praha ( 1974 ) 257 - 262 . Zbl 0326.05102 · Zbl 0326.05102
[4] I. Havel and P. Liebel , One legged caterpillars spans hypercubes . J. Graph Theory 10 ( 1986 ) 69 - 77 . Zbl 0589.05031 · Zbl 0589.05031
[5] I. Havel and P. Liebel , Embedding the dichotomie tree into the cube (Czech with english summary). Cas. Prest. Mat. 97 ( 1972 ) 201 - 205 . Zbl 0229.05109 · Zbl 0229.05109
[6] I. Havel and J. Moravek , B-valuations of graphs . Czech. Math. J. 22 ( 1972 ) 388 - 351 . Article | Zbl 0247.05148 · Zbl 0247.05148
[7] I. Havel , On hamiltonian circuits and spanning trees of hypercubes . Cas. prest. Mat. 109 ( 1984 ) 135 - 152 . Zbl 0544.05057 · Zbl 0544.05057
[8] L. Nebesky , On cubes and dichotomic trees . Cas Prest. Mat. 99 ( 1974 ). MR 354425 | Zbl 0277.05101 · Zbl 0277.05101
[9] L. Nebesky , On quasistars in n-cubes . Cas. Prest. Mat. 109 ( 1984 ) 153 - 156 . Zbl 0542.05029 · Zbl 0542.05029
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.