Please use this identifier to cite or link to this item:
Title: On equicut graphs
Authors: Deza, Michel.
Pasechnik, Dmitrii V.
Keywords: DRNTU::Science::Mathematics::Geometry
Issue Date: 2001
Source: Deza, M., & Pasechnik, D. V. (2001). On equicut graphs. Multiple-Valued Logic, 7, 363-377.
Series/Report no.: Multiple-valued logic
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.
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:
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
20. On equicut graphs.pdf202.82 kBAdobe PDFThumbnail

Google ScholarTM


Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.