On equicut graphs

Abstract

The size sz(T) of an l1-graph T = (V, E) is the minimum of nf/tf over all the possible l1-embeddings f into nf-dimensional hypercube with scale tf. The sum of distances between all the pairs of vertices of F is at most sz(T)[v/2][v/2] (v = \V\). The latter is an equality if and only if T is equicut graph, that is, T admits an l1 -embedding f that for any 1 <= i <= nf satisfies Exev f(x)i e {[v/2], [v/2]}. Basic properties of equicut graphs arc investigated. A construction of equicut graphs from l1-graphs via a natural doubling construction is given. It generalizes several well-known constructions of polytopes and distance-regular graphs. Finally, largo families of examples, mostly related to polytopes and distance-regular graphs, are presented.