On equicut graphs

• Main Authors: Deza, Michel., Pasechnik, Dmitrii V.
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2011
• Subjects: DRNTU::Science::Mathematics::Geometry
• Online Access: https://hdl.handle.net/10356/92187; http://hdl.handle.net/10220/6868; http://www.site.uottawa.ca/~ivan/mvl.html
• Institution: 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...