| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4647136 | Discrete Mathematics | 2016 | 8 Pages |
Abstract
In this paper, we study the diameter of these two families of polytopes. For a connected graph G, we prove that the diameter of CUT(G) is at most |V|â1, improving on the bound of |E| given by F. Barahona and A.R. Mahjoub. We also give its exact value for trees and complete bipartite graphs. Then, with respect to uniform cut polytopes, we introduce sufficient conditions for adjacency of two vertices in CUT=k(G), we study some particular cases and provide some connections with other partition polytopes from the literature.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
José Neto,