| Title:
|
A note on the cubical dimension of new classes of binary trees (English) |
| Author:
|
Kabyl, Kamal |
| Author:
|
Berrachedi, Abdelhafid |
| Author:
|
Sopena, Éric |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
65 |
| Issue:
|
1 |
| Year:
|
2015 |
| Pages:
|
151-160 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
The cubical dimension of a graph $G$ is the smallest dimension of a hypercube into which $G$ is embeddable as a subgraph. The conjecture of Havel (1984) claims that the cubical dimension of every balanced binary tree with $2^n$ vertices, $n\geq 1$, is $n$. The 2-rooted complete binary tree of depth $n$ is obtained from two copies of the complete binary tree of depth $n$ by adding an edge linking their respective roots. In this paper, we determine the cubical dimension of trees obtained by subdividing twice a 2-rooted complete binary tree and prove that every such balanced tree satisfies the conjecture of Havel. (English) |
| Keyword:
|
cubical dimension |
| Keyword:
|
embedding |
| Keyword:
|
Havel's conjecture |
| Keyword:
|
hypercube |
| Keyword:
|
tree |
| MSC:
|
05C05 |
| MSC:
|
05C60 |
| idZBL:
|
Zbl 06433726 |
| idMR:
|
MR3336030 |
| DOI:
|
10.1007/s10587-015-0165-6 |
| . |
| Date available:
|
2015-04-01T12:29:09Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144218 |
| . |
| Reference:
|
[1] Bezrukov, S., Monien, B., Unger, W., Wechsung, G.: Embedding ladders and caterpillars into the hypercube.Discrete Appl. Math. 83 (1998), 21-29. Zbl 0906.05019, MR 1622961, 10.1016/S0166-218X(97)00101-7 |
| Reference:
|
[2] Chen, C.-C., Chen, R.-J.: Compact embedding of binary trees into hypercubes.Inf. Process. Lett. 54 (1995), 69-72. Zbl 1022.68594, MR 1332424, 10.1016/0020-0190(95)00010-A |
| Reference:
|
[3] Choudum, S. A., Lavanya, S.: Embedding a subclass of trees into hypercubes.Discrete Math. 311 (2011), 866-871. Zbl 1223.05020, MR 2781631, 10.1016/j.disc.2011.02.011 |
| Reference:
|
[4] Choudum, S. A., Raman, I.: Embedding height balanced trees and Fibonacci trees in hypercubes.J. Appl. Math. Comput. 30 (2009), 39-52. Zbl 1193.68187, MR 2496600, 10.1007/s12190-008-0155-z |
| Reference:
|
[5] Dvořák, T.: Dense sets and embedding binary trees into hypercubes.Discrete Appl. Math. 155 (2007), 506-514. Zbl 1111.05023, MR 2296871, 10.1016/j.dam.2006.09.003 |
| Reference:
|
[6] Firsov, V. V.: On isometric embedding of a graph into a Boolean cube.Kibernetika 1965 Russian (1965), 95-96 Cybernetics 1 (1965), 112-113. MR 0210614, 10.1007/BF01074705 |
| Reference:
|
[7] Harary, F., Lewinter, M., Widulski, W.: On two-legged caterpillars which span hypercubes.Congr. Numer. 66 (1988), 103-108. Zbl 0692.05023, MR 0992892 |
| Reference:
|
[8] Havel, I.: On Hamiltonian circuits and spanning trees of hypercubes.Čas. Pěst. Mat. 109 (1984), 135-152. Zbl 0544.05057, MR 0744871 |
| Reference:
|
[9] Havel, I., Liebl, P.: Embedding the dichotomic tree into the $n$-cube.Čas. Pěst. Mat. 97 Czech (1972), 201-205. Zbl 0229.05109, MR 0306025 |
| Reference:
|
[10] Havel, I., Morávek, J.: {$B$}-valuations of graphs.Czech. Math. J. 22 (1972), 338-351. Zbl 0247.05148, MR 0294159 |
| Reference:
|
[11] Kobeissi, M., Mollard, M.: Spanning graphs of hypercubes: starlike and double starlike trees.Discrete Math. 244 (2002), 231-239. Zbl 0992.05032, MR 1844035, 10.1016/S0012-365X(01)00086-3 |
| Reference:
|
[12] Nebeský, L.: On cubes and dichotomic trees.Čas. Pěst. Mat. 99 (1974), 164-167. Zbl 0277.05101, MR 0354425 |
| Reference:
|
[13] Nekri, M., Berrachedi, A.: Two new classes of trees embeddable into hypercubes.RAIRO, Oper. Res. 38 (2004), 295-303. Zbl 1114.05023, MR 2178082, 10.1051/ro:2004027 |
| Reference:
|
[14] Wagner, A., Corneil, D. G.: Embedding trees in a hypercube is NP-complete.SIAM J. Comput. 19 (1990), 570-590. Zbl 0698.68054, MR 1041546, 10.1137/0219038 |
| . |
