On equicut graphs.

DSpace/Manakin Repository


Search DR-NTU

Advanced Search Subject Search


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