| Popis: |
Four kinds of dimensions μ i ( G ) of a finite graph G are defined and studied, i = 1, 2, 3, 4. Dimension μ 1 ( G ) is the “Sabidussi dimension” and μ 2 ( G ) coincides with the “isometric dimension” of G defined by R. L. Graham and P. M. Winkler. We list some properties of these dimensions and calculate their value in some particular cases: complete graphs, cycles, trees, (3,4)-connected graphs, and n-partite graphs Km 1 ,m 2 ….m n The dimension of a product is always the sum of those of the factors; this leads for instance to the value of the dimension of a hypercube and of an n-dimensional grid Pm 1 ▪ Pm 2 ▪ Pm n All proofs are omitted for shortness and can be found in [2], where some other results are also given. |
