On equicut graphs.

DSpace/Manakin Repository


Search DR-NTU

Advanced Search Subject Search


My Account

On equicut graphs.

Show simple item record

dc.contributor.author Deza, Michel.
dc.contributor.author Pasechnik, Dmitrii V.
dc.date.accessioned 2011-07-06T03:00:58Z
dc.date.available 2011-07-06T03:00:58Z
dc.date.copyright 2001
dc.date.issued 2011-07-06T03:00:58Z
dc.identifier.citation Deza, M., & Pasechnik, D. V. (2001). On equicut graphs. Multiple-Valued Logic, 7, 363-377.
dc.identifier.uri http://hdl.handle.net/10220/6868
dc.description.abstract 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.
dc.format.extent 13 p.
dc.language.iso en
dc.relation.ispartofseries Multiple-valued logic
dc.rights © 2001 Taylor & Francis. This is the author created version of a work that has been peer reviewed and accepted for publication by Multiple-Valued Logic, Taylor & Francis. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at the following URL: http://www.site.uottawa.ca/~ivan/mvl.html.
dc.subject DRNTU::Science::Mathematics::Geometry.
dc.title On equicut graphs.
dc.type Journal Article
dc.contributor.school School of Physical and Mathematical Sciences
dc.identifier.openurl http://www.site.uottawa.ca/~ivan/mvl.html
dc.description.version Accepted version

Files in this item

Files Size Format View
20. On equicut graphs.pdf 207.6Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record


Total views

All Items Views
On equicut graphs. 346

Total downloads

All Bitstreams Views
20. On equicut graphs.pdf 192

Top country downloads

Country Code Views
China 63
United States of America 63
Singapore 12
France 8
Unknown Country 6

Top city downloads

city Views
Beijing 50
Mountain View 37
Singapore 12
Tabriz 5
Southampton 4