JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 3, No 2 (1994)

M. Deza and M. Laurent

An ₁-graph is a graph whose nodes can be labeled by binary vectors in such a way that the Hamming distance between the binary addresses is, up to scale, the distance in the graph between the corresponding nodes. We show that many interesting graphs are ₁-rigid, i.e., that they admit an essentially unique such binary labeling.

1. P. Assouad, "Embeddability of regular polytopes and honeycombs in hypercubes," The Geometric Vein, Springer, 1981, pp. 141-147.
2. P. Assouad and M. Deza, "Metric subspaces of L1," Publications mathematiques d'Orsay 3 (1982).
3. I.F. Blake and J.H. Gilchrist, "Addresses for graphs," IEEE Trans. Inform. Theory 5 (1973), 683-688.
4. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer Verlag, 1989.
5. J.H. Conway and N.J.A. Sloane, Sphere packings, lattices and groups, Grundlehren der mathematischen Wissenschaften, Springer Verlag, Berlin, 290, 1987.
6. H.S.M. Coxeter, Regular Polytopes. Dover Publications, 1973.
7. D. Cvetkovic, M. Doob, I. Gutman, and A. Torgasev, "Recent results in the theory of graph spectra," Ann. Discrete Math. 36, (1988).
8. D. Cvetkovic, M. Doob, and H. Sachs, Spectra of Graphs-Theory and Applications, Academic Press, 1980.
9. M. Deza, "Une propriete extremale des plans projectifs finis dans une classe de codes equidistants," Discrete Math. 6 (1973), 343-352.
10. M. Deza and V.P. Grishukhin, "Hypermetric graphs," Q. J. Math. Oxford (2) 44 (1993), 399-433.
11. M. Deza, V.P. Grishukhin, and M. Laurent, "Extreme hypermetrics and L-polytopes," in Sets, Graphs and Numbers, Budapest, 1991, Colloquia Mathematica Societatis Janos Bolyai, vol. 60, 1992, 157-209.
12. M. Deza and M. Laurent, "Applications of cut polyhedra," LIENS-92-18, Ecole Normale Superieure, Paris, 1992 (to appear in J. Comp. Appl. Math.).
13. M. Deza and M. Laurent, "Extension operations for cuts," Discrete Math. 106-107 (1992), 163-179.
14. M. Deza and M. Laurent, "Facets for the cut cone I," Math. Prog. 56 (1992), 121-160.
15. M. Deza and M. Laurent, "Variety of hypercube embeddings of the equidistant metric and designs," J. Combin. Information System Sci. 18 (1993).
16. M. Deza and M. Laurent, "The cut cone; Simplicial faces and linear dependencies." Bull. Inst, Math. Academia Sinica, 21 (1993), 143-182.
17. M. Deza and N.M. Singhi, "Rigid pentagons in hypercubes," Graphs and Combin. 4 (1988), 31-42.
18. D.Z. Djokovic, "Distance preserving subgraphs of hypercubes," J. Combin. Theory Series B 14 (1973), 263-267.
19. R.L. Graham and P.M. Winkler, "On isometric embeddings of graphs," Trans. Amer. Math. Society 288 (1985), 527-536.
20. A.V. Karzanov, "Metrics and undirected cuts," Math. Prog. 32 (1985), 183-198.
21. J. Koolen, "On metric properties of regular graphs," Master's thesis, Eindhoven University of Technology, 1990.
22. M. Lomonossov and A. Sebo, "On the geodesic-structure of graphs: a polyhedral approach to metric decomposition," in Integer Programming and Combinatorial Optimization, Erice, 1993, 221-234.
23. R.L. Roth and P.M. Winkler, "Collapse of the metric hierarchy for bipartite graphs," European J. Combin. 7 (1986), 371-375.
24. S.V. Shpectorov, "On scale embeddings of graphs into hypercubes," European J. Combin. 14 (1993), 117-130.
25. P.M. Weichsel, "Distance regular subgraphs of a cube," Discrete Math. 109 (1992), 297-306.
26. P.M. Winkler, "The metric structure of graphs: theory and applications," in Surveys in Combinatorics 1987, C. Whitehead, ed., London Mathematical Society, Lecture Note Series 123, Cambridge University Press, Cambridge, 1987, pp. 197-221.