×

On isometric embeddings of graphs. (English) Zbl 0576.05017

In a connected undirected graph G the metric is defined in a standard way. Using this metric one can define a special equivalence \({\hat \Theta}\) on the edge set of G, from which a new graph \(\pi G^*_ i\) is constructed. Every factor \(G^*_ i\) corresponds to one of the equivalence classes of \({\hat \Theta}\). Finally a canonical embedding of G into \(\pi G^*_ i\) is described. It is proved, that the canonical embedding is isometric, is irredundant (i.e. every factor \(G^*_ i\) has two vertices at least), has irreducible factors and has the largest possible number of factors among all irreducible isometric embeddings of G. In 1973 Graham and Pollak proved, that the distance matrix of every tree on n vertices has its determinant equal to \((-1)^ nn2^{n-1}\). The authors generalized this theorem for full dimensional cubes and for a full dimensional family of subsets of \(\{\) 1,2,...,n\(\}\). The next theorem is also proposed: The isometric embedding of a graph G in n-cube exists iff dimension G (i.e. the number of factors in \(\pi G^*_ i)\) is equal to the number of negative eigenvalues of the distance matrix of G.
Reviewer: M.Koman

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Patrice Assouad, Un espace hypermétrique non plongeable dans un espace \?\(_{1}\), C. R. Acad. Sci. Paris Sér. A-B 285 (1977), no. 5, A361 – A363 (French, with English summary). · Zbl 0367.52014
[2] -, 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.
[3] -, Sur les inequalités valides dans \( {L^1}\), Preprint.
[4] Patrice Assouad and Charles Delorme, Graphes plongeables dans \?\textonesuperior , C. R. Acad. Sci. Paris Sér. A-B 291 (1980), no. 6, A369 – A372 (French, with English summary). · Zbl 0446.05020
[5] -, Distances sur les graphes et plongements dans \( {L^1}\). I, II, Preprints.
[6] P. Assouad and M. Deza, Espaces métriques plongeables dans un hypercube: aspects combinatoires, Ann. Discrete Math. 8 (1980), 197 – 210 (French). Combinatorics 79 (Proc. Colloq., Univ. Montréal, Montreal, Que., 1979), Part I. · Zbl 0464.05029
[7] -, Metric subspaces of \( {L^1}\), Preprint.
[8] D. Avis, Hamming metrics and facets of the Hamming cone, Tech. Report SOCS-78.4, School of Comp. Sci., McGill University, 1978.
[9] David Avis, Extremal metrics induced by graphs, Ann. Discrete Math. 8 (1980), 217 – 220. Combinatorics 79 (Proc. Colloq., Univ. Montréal, Montreal, Que., 1979), Part I. · Zbl 0469.05042
[10] David Avis, Hypermetric spaces and the Hamming cone, Canad. J. Math. 33 (1981), no. 4, 795 – 802. · Zbl 0445.52008
[11] J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976. · Zbl 1226.05083
[12] L. H. Brandenburg, B. Gopinath, and R. P. Kurshan, On the addressing problem of loop switching, Bell. System Tech. J. 51 (1972), 1445 – 1469. · Zbl 0242.94030
[13] A. K. Dewdney, The embedding dimension of a graph, Ars Combin. 9 (1980), 77 – 90. · Zbl 0458.05030
[14] M. E. Tylkin, On Hamming geometry of unitary cubes, Soviet Physics. Dokl. 5 (1960), 940 – 943.
[15] -, Realizability of matrices of distances in unitary cubes, Problemy Kibernet. 7 (1962), 31-42. (Russian)
[16] D. Ž. Djoković, Distance-preserving subgraphs of hypercubes, J. Combinatorial Theory Ser. B 14 (1973), 263 – 267. · Zbl 0245.05113
[17] M. Edelberg, M. R. Garey, and R. L. Graham, On the distance matrix of a tree, Discrete Math. 14 (1976), no. 1, 23 – 39. · Zbl 0328.05103
[18] 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).
[19] F. R. Gantmacher, The theory of matrices, vol. I, Chelsea, New York, 1959. · Zbl 0085.01001
[20] R. L. Graham and H. O. Pollak, On the addressing problem for loop switching, Bell System Tech. J. 50 (1971), 2495 – 2519. · Zbl 0228.94020
[21] 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), Springer, Berlin, 1972, pp. 99 – 110. Lecture Notes in Math., Vol. 303. · Zbl 0251.05123
[22] 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. · Zbl 0363.05034
[23] R. L. Graham and L. Lovász, Distance matrix polynomials of trees, Adv. in Math. 29 (1978), no. 1, 60 – 88. · Zbl 0382.05023
[24] 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. · Zbl 0223.52014
[25] 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.
[26] John B. Kelly, Hypermetric spaces, The geometry of metric and linear spaces (Proc. Conf., Michigan State Univ., East Lansing, Mich., 1974) Springer, Berlin, 1975, pp. 17 – 31. Lecture Notes in Math., Vol. 490.
[27] H. J. Landau, Personal Communication.
[28] P. M. Winkler, On graphs which are metric spaces of negative type (in preparation). · Zbl 0576.05049
[29] Andrew Chi Chih Yao, On the loop switching addressing problem, SIAM J. Comput. 7 (1978), no. 4, 515 – 523. · Zbl 0386.68063
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.