On the dimension of trees |
| |
Authors: | S. Poljak A. Pultr |
| |
Affiliation: | Math.-Phys. Faculty, Charles University, Sokolovská 83, 18600 Praha 8, Czechoslovakia |
| |
Abstract: | It is proved that for trees (and forests) G one has dimG?3 log+2∣G∣(where dim G, the dimension of G, is the minimum k such that G is embeddable into a product of k complete graphs; ∣G∣ is the size of G). Moreover, if m(G) is the quotient of G obtained by identifying the points with coinciding neighbour sets, one has, for forests G, log+2 ∣m(G)∣ ? 1 ? dimG ? 3 log+2m(G>) + 1. Also, for the bipartite dimension bid G (arising from embeddings into Pk3) one has bid G ? 8 log+2 ∣G ∣. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|