Journal article
On equicut graphs
- Abstract:
-
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 inv...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Authors
Bibliographic Details
- Publisher:
- Taylor and Francis Publisher's website
- Journal:
- Multiple Valued Logic: An International Journal
- Volume:
- 7
- Pages:
- 363–377
- Publication date:
- 2001-01-01
- ISSN:
-
1023-6627
- Source identifiers:
-
446351
Item Description
- Keywords:
- Pubs id:
-
pubs:446351
- UUID:
-
uuid:f619d170-0c01-4127-80cd-98067925b4ff
- Local pid:
- info:fedora/pubs:446351
- Deposit date:
- 2016-07-28
Terms of use
- Copyright holder:
- Taylor & Francis Ltd
- Copyright date:
- 2001
- Notes:
-
This is a
pre-print version of a journal article published by Taylor & Francis in Multiple Valued Logic: An International Journal in 2001
If you are the owner of this record, you can report an update to it here: Report update to this record