mirage

On equicut graphs.

DSpace/Manakin Repository

 

Search DR-NTU


Advanced Search Subject Search

Browse

My Account

On equicut graphs.

Show full item record

Title: On equicut graphs.
Author: Deza, Michel.; Pasechnik, Dmitrii V.
Copyright year: 2001
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.
Subject: DRNTU::Science::Mathematics::Geometry.
Type: Journal Article
Series/ Journal Title: Multiple-valued logic
School: School of Physical and Mathematical Sciences
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.
Version: Accepted version

Files in this item

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

SFX Query

- Get published version (via NTU subscribed resources)
   

This item appears in the following Collection(s)

Show full item record

Statistics

Total views

All Items Views
On equicut graphs. 269

Total downloads

All Bitstreams Views
20. On equicut graphs.pdf 157

Top country downloads

Country Code Views
United States of America 50
China 48
Singapore 12
Unknown Country 6
United Kingdom 6

Top city downloads

city Views
Beijing 38
Mountain View 29
Singapore 12
Tabriz 5
Southampton 4