Metric transforms of finite spaces and connected graphs. (English) Zbl 0592.05058
Summary: A metric transform of a semimetric space X is obtained from X by measuring the distances by a different (not always proportional) scale. Two semimetric spaces are said to be isomorphic if one is isometric to a metric transform of the other. If X is a finite semimetric space, then it will be shown that X is isomorphic to a subset of a Euclidean space. The dimension of X is defined to be the minimum dimension of a Euclidean space containing an isomorph of X. In this paper we examine scales and dimensions for finite semimetric spaces, especially, for connected graphs and trees as metric spaces. We also count the number of non-isomorphic semimetric spaces.
MSC:
| 05C99 | Graph theory |
| 05C05 | Trees |
| 54E25 | Semimetric spaces |
| 05C30 | Enumeration in graph theory |
| 54E35 | Metric spaces, metrizability |
References:
| [1] | Assouad, P.; Deza, M., Espaces métriques plongeables dans un hypercube: Aspects combinatoires, Ann. Discrete Math., 8, 197-210 (1980) · Zbl 0464.05029 |
| [2] | Blumenthal, L. M., Theory and Applications of Distance Geometry (1970), Chelsea: Chelsea New York · Zbl 0208.24801 |
| [3] | Graham, R. L.; Pollak, H. O., On embedding graphs in squashed cubes, (Graph Theory and Applications, Lecture Notes in Mathematics 303 (1972), Springer-Verlag), (Proc. of conference held at Western Michigan University, May 10-13, 1972) · Zbl 0251.05123 |
| [4] | Harary, F.; Palmer, E. M., Graphical Enumeration (1973), Academic Press: Academic Press New York · Zbl 0266.05108 |
| [5] | von Neumann, J.; Schoenberg, I. J., Fourier integrals and metric geometry, Trans. Amer. Math. Soc., 50, 226-251 (1941) · Zbl 0028.41002 |
| [6] | Riordan, J., Combinatorial Identities (1968), Wiley: Wiley New York · Zbl 0194.00502 |
| [7] | Schoenberg, I. J., Remarks to Maurice Frechet’s article…, Ann. Math., 36, 724-732 (1935) · Zbl 0012.30703 |
| [8] | Schoenberg, I. J., Metric space and completely monotone functions, Ann. Math., 39, 811-841 (1938) · Zbl 0019.41503 |
| [9] | Winkler, P. M., Proof of squashed cube conjecture, Combinatorica, 3, 1, 135-139 (1983) · Zbl 0522.05064 |
| [10] | Winkler, P. M., Isometric embedding in products of complete graphs, Discrete Appl. Math., 7, 221-225 (1984) · Zbl 0529.05055 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
