✦ LIBER ✦

An upper bound for the diameter of a polytope

✍ Scribed by David Barnette

Publisher: Elsevier Science
Year: 1974
Tongue: English
Weight: 515 KB
Volume: 10
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(74)90016-8

No coin nor oath required. For personal study only.

✦ Synopsis

The distance between two vertices of a polytope is the minimum number of edges in a path joining them. The diameter of a polytope is the greatest distance between two vertices of the polytope. We show that if P is a d-dimensional polytope with n facets, then the diameter of P is at most $ $-3(,r -d + 3).

📜 SIMILAR VOLUMES

An Upper Bound Theorem for Rational Poly

An Upper Bound Theorem for Rational Polytopes

✍ Margaret M Bayer 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 190 KB

The upper bound inequality h i (P)&h i&1 (P) ( n&d+i&2 i ) (0 i dÂ2) is proved for the toric h-vector of a rational convex d-dimensional polytope with n vertices. This gives nonlinear inequalities on flag vectors of rational polytopes. ## 1998 Academic Press A major result in polytope theory is th

Upper Bounds on the Maximal Number of Fa

Upper Bounds on the Maximal Number of Facets of 0/1-Polytopes

✍ Tamás Fleiner; Volker Kaibel; Günter Rote 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 157 KB

We prove two new upper bounds on the number of facets that a d-dimensional 0/1-polytope can have. The first one is 2(d -1)!+2(d -1) (which is the best one currently known for small dimensions), while the second one of O((d -2)!) is the best known bound for large dimensions.

An upper bound for the path number of a

An upper bound for the path number of a graph

✍ Alan Donald 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 529 KB

## Abstract The path number of a graph __G__, denoted __p(G)__, is the minimum number of edge‐disjoint paths covering the edges of __G.__ Lovász has proved that if __G__ has __u__ odd vertices and __g__ even vertices, then __p(G)__ ≤ 1/2 __u__ + __g__ ‐ 1 ≤ __n__ ‐ 1, where __n__ is the total numbe

Upper bound for the degree of an approxi

Upper bound for the degree of an approximating monomial

✍ Sayel A Ali 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 929 KB

An upper bound for the complexity of tra

An upper bound for the complexity of transformation semigroups

✍ Stuart W Margolis; Bret Tilson 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 759 KB

An upper bound for the harmonious chroma

An upper bound for the harmonious chromatic number of a graph

✍ Sin-Min Lee; John Mitchem 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB 👁 2 views

An upper bound for the harmonious chromatic number of a graph G is given. Three corollaries of the theorem are theorems or improvements of the theorems of Miller and Pritikin. The assignment of colors to the vertices of a graph such that each vertex has exactly one color has been studied for well o