摘要: An \ell_1-graph is a graph whose nodes can be labeled by binary vectors in such way that the Hamming distance between addresses is, up to scale, corresponding nodes. We show many interesting graphs are \ell_1-rigid, i.e., they admit an essentially unique labeling.
springer.com
paperity.org参考文章(22)
Paul M. Weichsel, Distance regular subgraphs of a cube Discrete Mathematics. ,vol. 109, pp. 297- 306 ,(1992) , 10.1016/0012-365X(92)90300-5
András Sebö, Michael Lomonosov, On the geodesic-structure of graphs: a polyhedral approach to metric decomposition. integer programming and combinatorial optimization. pp. 221- 234 ,(1993)
Patrice Assouad, Embeddability of Regular Polytopes and Honeycombs in Hypercubes Springer New York. pp. 141- 147 ,(1981) , 10.1007/978-1-4612-5648-9_8
Patrice Assouad, M. Deza, Metric subspaces of L[1] Université de Paris-Sud, Département de Mathématique. ,(1982)
Michael Doob, Aleksandar Torgašev, Dragoš M. Cvetković, Ivan Gutman, Recent Results in the Theory of Graph Spectra ,(1988)
Michael Doob, Dragoš M. Cvetković, Horst Sachs, Spectra of graphs : theory and application Johann Ambrosius Barth Verlag. ,(1995)
Michel Deza, Monique Laurent, Applications of cut polyhedra—II Journal of Computational and Applied Mathematics. ,vol. 55, pp. 191- 216 ,(1994) , 10.1016/0377-0427(94)90020-5
E. Bannai, N. J. A. Sloane, J. H. Conway, Sphere packings, lattices, and groups ,(1987)
M. Deza, N. M. Singhi, Rigid pentagons in hypercubes Graphs and Combinatorics. ,vol. 4, pp. 31- 42 ,(1988) , 10.1007/BF01864151
A. V. Karzanov, Metrics and undirected cuts Mathematical Programming. ,vol. 32, pp. 183- 198 ,(1985) , 10.1007/BF01586090