On equicut graphs

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Deza, Michel., Pasechnik, Dmitrii V.
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2011
Subjects:
Online Access:https://hdl.handle.net/10356/92187
http://hdl.handle.net/10220/6868
http://www.site.uottawa.ca/~ivan/mvl.html
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary: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 equicut graph, that is, Γ admits an ℓ1-embedding f that for any 1 ≤ i ≤ nf satisfies Σx∈X f(x)i ∈ {⌈v/2⌉, ⌊v/2⌋} for any x ∈ V . Basic properties of equicut graphs are investigated. A construction of equicut graphs from ℓ1-graphs via a natural doubling construction is given. It generalizes several well-known constructions of polytopes and distance-regular graphs. Finally, large families of examples, mostly related to polytopes and distance-regular graphs, are presented.