The minimum number of vertices of a simple polytope

Ad-polytope is ad-dimensional set that is the convex hull of a finite number of points. Ad-polytope is simple provided each vertex meets exactlyd edges. It has been conjectured that for simple polytopes {fx121-1} wheref _i is the number ofi-dimensional faces of the polytope. In this paper we show that inequality (i) holds for all simple polytopes. Research supported by N.S.F. Grant GP-19221.     

The vertices of the knapsack polytope

The number of vertices of a polytope associated to the Knapsack integer programming problem is shown to be small. An algorithm for finding these vertices is discussed.     

A lower bound theorem for polytope pairs

V. Klee has generalized the lower bound theorem of D. Barnette for polytope pairs. He has extensively studied polytope pairs. Here, two theorems for polytope pairs, which are analogous to those of Barnette and lead to more open problems for polytope pairs, are proved. Two theorems of Klee and two of Barnette are immediate corollaries of the theorems.     

An upper bound for the diameter of a polytope

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 $\text{1}\text{3}\text{2}{}^{\mathrm{d?3}}\text{(n?d+}\text{5}\text{2}\text{)}$.     

Computational results on an algorithm for finding all vertices of a polytope

This paper provides answers to several questions raised by V. Klee regarding the efficacy of Mattheiss' algorithm for finding all vertices of convex polytopes. Several results relating to the expected properties of polytopes are given which indicate thatn-polytopes defined by large numbers of constraints are difficult to obtain by random processes, the expected value of the number of vertices of polytope is considerably less than Klee's least upper bound the expected performance of Mattheiss' algorithm is far better than Klee's upper bound would suggest.     

Disjoint edge paths between given vertices of a convex polytope

A Gale diagram technique is used to show that if d is positive integer greater than one, then there is a d-polytope P such that there are [$\text{2(d + 4)}\text{5}$] pairs of distinct vertices of P which cannot all be joined by disjoint paths in the graph of P.     

On the product of the distances of a point from the vertices of a polytope

Letx ₁,...,x _m be points in the solid unit sphere ofE _n and letx belong to the convex hull ofx ₁,...,x _m. Then . This implies that all such products are bounded by (2/m) ^m (m −1) ^m−1. Bounds are also given for other normed linear spaces. As an application a bound is obtained for |p(z ₀)| where andp′(z ₀)=0.     

Point-color-symmetric graphs with a prime number of vertices

We construct and enumerate all point-color-symmetric digraphs and graphs with a prime number of vertices. Our result unifies and generalizes the similar results for vertex transitive graphs and symmetric graphs.     

Nonflexible polyhedra with a small number of vertices

The paper shows which embedded and immersed polyhedra with no more than eight vertices are nonflexible. It turns out that all embedded polyhedra are nonflexible, except possibly for polyhedra of one of the combinatorial types, for which the problem still remains open. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 12, No. 1, pp. 143–165, 2006.     

A lower bound on the vertices of Specht modules for symmetric groups

In this paper we study the vertices of indecomposable Specht modules for symmetric groups. For any given indecomposable non-projective Specht module, the main theorem of the article describes a p-subgroup contained in its vertex. The theorem generalizes and improves an earlier result due to Wildon in [13].     

A lower bound for the interval number of a graph

The interval number i(G) of a graph G with n vertices is the lowest integer m such that G is the intersection graph of some family of sets I₁,…,I_n with every I_i being the union of at most m real intervals. In this article a lower bound for i(G) is proved followed by some considerations about the construction of graphs that are critical with respect to the interval number.     

A bound for the number of tournaments with specified scores

Let $\text{T}$(R) denote the set of all tournaments with score vector R = (r₁, r₂,…, r_n). R. A. Brualdi and Li Qiao (“Proceedings of the Silver Jubilee Conference in Combinatorics at Waterloo,” in press) conjectured that if R is strong with r₁ ≤ r₂ ≤ … ≤ r_n, then |$\text{T}$(R)| ≥ 2^n?2 with equality if and only if R = (1, 1, 2,…, n ? 3, n ? 2, n ? 2). In this paper their conjecture is proved, and this result is used to establish a lower bound on the cardinality of $\text{T}$(R) for every R.     

The product of the distances of a point inside a regular polytope to its vertices

We show that the maximum of the product of the distances from a point inside an n-dimensional regular simplex, cross-polytope or cube to the vertices is attained at the midpoint of an edge for small n, but is attained at symmetrically placed pairs on an edge for sufficiently high dimensions. We also examine the problem for regular polygons and general triangles in the plane. Murray Klamkin passed away on August 15, 2004. He was Professor of Mathematics at the University of Alberta, Edmonton, Alberta, Canada.     

Combinatorial structure and adjacency of vertices of polytope of b-factors

In the present paper in terms of the graph theory we describe the structure and vertices adjacency criterion of b-factors polyhedron. The special attention is paid to nonintegral vertices. Results of the present paper, in particular, generalize properties of nonintegral vertices of TSP polyhedron, give vertices adjacency criterion of a transportation polytope.     

On labeled vertex-transitive digraphs with a prime number of vertices

We enumerate, up to isomorphism, several classes of labeled vertex-transitive digraphs with a prime number of vertices.     

A lower bound for the independence number of a planar graph

A subset of the vertices of a graph is independent if no two vertices in the subset are adjacent. The independence number α(G) is the maximum number of vertices in an independent set. We prove that if G is a planar graph on N vertices then $\text{α(G)/N ?}\text{2}\text{9}$.