On equicut graphs
| dc.creator | Deza, Michel | |
| dc.creator | Pasechnik, Dmitrii V. | |
| dc.date | 1999-09-30 | |
| dc.date.accessioned | 2026-07-07T05:30:58Z | |
| dc.date.available | 2026-07-07T05:30:58Z | |
| dc.description | 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. | |
| dc.description | 13 pages | |
| dc.identifier | https://arxiv.org/abs/math/9909185 | |
| dc.identifier | http://arxiv.org/abs/math/9909185 | |
| dc.identifier | Multi. Val. Logic. 7(2001) pp. 363--377 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/79178 | |
| dc.subject | Combinatorics | |
| dc.subject | Metric Geometry | |
| dc.subject | 05C12; 52B12 | |
| dc.title | On equicut graphs | |
| dc.type | text |