|
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 |
