On equicut graphs

Details On equicut graphs On equicut graphs

1999-09-30

arxiv.org/abs/math/9909185v1

Multi. Val. Logic. 7(2001) pp. 363--377

Mathematics

Combinatorics

13 pages

Scientific paper

The size sz(G) of an l_1-graph G=(V,E) is the minimum of n_f/t_f over all its possible l_1-embeddings f into n_f-dimensional hypercube with scale t_f. In terms of v=|V|, the sum of distances between all the pairs of vertices of G is at most sz(G) v^2/4 for v even, (resp. sz(G)(v-1)(v+1)/4 for v odd). This bound is reached if and only if G is an equicut graph, that is, G admits an l_1-embedding with column sums v/2, v even (resp. (v-1)/2 for v odd). Basic properties of equicut graphs are investigated. A construction of equicut graphs from l_1-graphs via a natural doubling construction is given. It generalizes several well-known constructions of polytopes and distance-regular graphs. Large families of examples, mostly related to polytopes and distance-regular graphs, are presented.

Affiliated with

Also associated with

No associations

Rating

On equicut graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On equicut graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On equicut graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-570674