On equicut graphs

• Main Authors: Deza, Michel., Pasechnik, Dmitrii V.
• 其他作者: School of Physical and Mathematical Sciences
• 格式: Article
• 語言: English
• 出版: 2011
• 主題: DRNTU::Science::Mathematics::Geometry
• 在線閱讀: https://hdl.handle.net/10356/92187; http://hdl.handle.net/10220/6868; http://www.site.uottawa.ca/~ivan/mvl.html
• 機構: Nanyang Technological University

The size sz(Γ) of an ℓ1-graph Γ = (V, E) is the minimum of nf/tf over all the possible ℓ1-embeddings f into nf -dimensional hypercube with scale tf. The sum of distances between all the pairs of vertices of Γ is at most sz(Γ)⌈v/2⌉⌊v/2⌋ (v = |V |). The latter is an equality if and only if Γ is equicu...