On isometric embeddings of graphs
HTML articles powered by AMS MathViewer
- by R. L. Graham and P. M. Winkler
- Trans. Amer. Math. Soc. 288 (1985), 527-536
- DOI: https://doi.org/10.1090/S0002-9947-1985-0776391-5
- PDF | Request permission
Corrigendum: Trans. Amer. Math. Soc. 294 (1986), 379.
Abstract:
If $G$ is a finite connected graph with vertex set $V$ and edge set $E$, a standard way of defining a distance ${d_G}$ on $G$ is to define ${d_G}(x,y)$ to be the number of edges in a shortest path joining $x$ and $y$ in $V$. If $(M,{d_M})$ is an arbitrary metric space, then an embedding $\lambda :V \to M$ is said to be isometric if ${d_G}(x,y) = {d_M}(\lambda (x),\lambda (y))$ for all $x,y \in V$. In this paper we will lay the foundation for a theory of isometric embeddings of graphs into cartesian products of metric spaces.References
- Patrice Assouad, Un espace hypermétrique non plongeable dans un espace $L_{1}$, C. R. Acad. Sci. Paris Sér. A-B 285 (1977), no. 5, A361–A363 (French, with English summary). MR 448017 —, Plongements isométrique dans ${L^1}$: Aspect analytique, Sém. d’Initiation à l’Analyse (Paris 6), exposé no. 14, 1979-1980, Univ. of Paris VI. —, Sur les inequalités valides dans ${L^1}$, Preprint.
- Patrice Assouad and Charles Delorme, Graphes plongeables dans $L^{1}$, C. R. Acad. Sci. Paris Sér. A-B 291 (1980), no. 6, A369–A372 (French, with English summary). MR 596074 —, Distances sur les graphes et plongements dans ${L^1}$. I, II, Preprints.
- P. Assouad and M. Deza, Espaces métriques plongeables dans un hypercube: aspects combinatoires, Ann. Discrete Math. 8 (1980), 197–210 (French). MR 597174 —, Metric subspaces of ${L^1}$, Preprint. D. Avis, Hamming metrics and facets of the Hamming cone, Tech. Report SOCS-78.4, School of Comp. Sci., McGill University, 1978.
- David Avis, Extremal metrics induced by graphs, Ann. Discrete Math. 8 (1980), 217–220. MR 597176
- David Avis, Hypermetric spaces and the Hamming cone, Canadian J. Math. 33 (1981), no. 4, 795–802. MR 634138, DOI 10.4153/CJM-1981-061-5
- J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976. MR 0411988
- L. H. Brandenburg, B. Gopinath, and R. P. Kurshan, On the addressing problem of loop switching, Bell System Tech. J. 51 (1972), 1445–1469. MR 351603, DOI 10.1002/j.1538-7305.1972.tb02663.x
- A. K. Dewdney, The embedding dimension of a graph, Ars Combin. 9 (1980), 77–90. MR 582281
- M. E. Tylkin, On Hamming geometry of unitary cubes, Soviet Physics Dokl. 5 (1960), 940–943. MR 0122636 —, Realizability of matrices of distances in unitary cubes, Problemy Kibernet. 7 (1962), 31-42. (Russian)
- D. Ž. Djoković, Distance-preserving subgraphs of hypercubes, J. Combinatorial Theory Ser. B 14 (1973), 263–267. MR 314669, DOI 10.1016/0095-8956(73)90010-5
- M. Edelberg, M. R. Garey, and R. L. Graham, On the distance matrix of a tree, Discrete Math. 14 (1976), no. 1, 23–39. MR 411991, DOI 10.1016/0012-365X(76)90003-0
- V. V. Firsov, On isometric embedding of a graph into a Boolean cube, Kibernetika (Kiev) 1965 (1965), no. 6, 95–96 (Russian, with English summary). MR 210614 F. R. Gantmacher, The theory of matrices, vol. I, Chelsea, New York, 1959.
- R. L. Graham and H. O. Pollak, On the addressing problem for loop switching, Bell System Tech. J. 50 (1971), 2495–2519. MR 289210, DOI 10.1002/j.1538-7305.1971.tb02618.x
- R. L. Graham and H. O. Pollak, On embedding graphs in squashed cubes, Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), Lecture Notes in Math., Vol. 303, Springer, Berlin, 1972, pp. 99–110. MR 0332576
- R. L. Graham, A. J. Hoffman, and H. Hosoya, On the distance matrix of a directed graph, J. Graph Theory 1 (1977), no. 1, 85–88. MR 505769, DOI 10.1002/jgt.3190010116
- R. L. Graham and L. Lovász, Distance matrix polynomials of trees, Adv. in Math. 29 (1978), no. 1, 60–88. MR 480119, DOI 10.1016/0001-8708(78)90005-1
- John B. Kelly, Metric inequalities and symmetric differences, Inequalities, II (Proc. Second Sympos., U.S. Air Force Acad., Colo., 1967) Academic Press, New York, 1970, pp. 193–212. MR 0264600
- John B. Kelly, Hypermetric spaces and metric transforms, Inequalities, III (Proc. Third Sympos., Univ. California, Los Angeles, Calif., 1969; dedicated to the memory of Theodore S. Motzkin), Academic Press, New York, 1972, pp. 149–158. MR 0339086
- John B. Kelly, Hypermetric spaces, The geometry of metric and linear spaces (Proc. Conf., Michigan State Univ., East Lansing, Mich., 1974) Lecture Notes in Math., Vol. 490, Springer, Berlin, 1975, pp. 17–31. MR 0405367 H. J. Landau, Personal Communication. P. M. Winkler, On graphs which are metric spaces of negative type (in preparation).
- Andrew Chi Chih Yao, On the loop switching addressing problem, SIAM J. Comput. 7 (1978), no. 4, 515–523. MR 508611, DOI 10.1137/0207041
Bibliographic Information
- © Copyright 1985 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 288 (1985), 527-536
- MSC: Primary 05C10; Secondary 51K99
- DOI: https://doi.org/10.1090/S0002-9947-1985-0776391-5
- MathSciNet review: 776391