Geodesics on the regular tetrahedron and the cube

Consider all geodesics between two given points on a polyhedron. On the regular tetrahedron, we describe all the geodesics from a vertex to a point, which could be another vertex. Using the Stern–Brocot tree to explore the recursive structure of geodesics between vertices on a cube, we prove, in some precise sense, that there are twice as many geodesics between certain pairs of vertices than other pairs. We also obtain the fact that there are no geodesics that start and end at the same vertex on the regular tetrahedron or the cube.     

Rigidity of certain polyhedra in $ {\bold R}^3 $

We extend the Cauchy theorem stating rigidity of convex polyhedra in . We do not require that the polyhedron be convex nor embedded, only that the realization of the polyhedron in be linear and isometric on each face. We also extend the topology of the surfaces to include the projective plane in addition to the sphere. Our approach is to choose a convenient normal to each face in such a way that as we go around the star of a vertex the chosen normals are the vertices of a convex polygon on the unit sphere. When we can make such a choice at each vertex we obtain rigidity. For example, we can prove that the heptahedron is rigid. Received: March 3, 1999; revised: December 7, 1999.     

Integer Partitions from the Polyhedral Point of View

We characterize integer partitions that are convex combinations of two partitions, which connects vertices of the partition polytopes with Sidon sets and sum-free sets. We prove that all vertices of the partition polytope can be generated from a subset of support vertices with the use of two operations of merging parts. Application of either operation results in an adjacent vertex. We present also some numerical data on vertices.     

Vertex-faithful regular polyhedra

We study the abstract regular polyhedra with automorphism groups that act faithfully on their vertices, and show that each non-flat abstract regular polyhedron covers a “vertex-faithful” polyhedron with the same number of vertices. We then use this result and earlier work on flat polyhedra to study abstract regular polyhedra based on the size of their vertex set. In particular, we classify all regular polyhedra where the number of vertices is prime or twice a prime. We also construct the smallest regular polyhedra with a prime squared number of vertices.     

Polyhedra related to a lattice

Without using the l.p. duality theorem, we give a new and direct proof that Hoffman's lattice polyhedra, polyhedra from problems of Edmonds and Giles, and others, are integer. These polyhedra are intersections of more simple polyhedra such that every vertex of the initial polyhedron is a vertex of some simple polyhedron. In many cases encountered in combinatorics the simple polyhedra have a totally unimodular constraint matrix. This implies that all vertices of the initial polyhedron are integral. The proof is based on a theorem on submodular functions, which was not known earlier. The method of this paper can be applied to the consideration of the matching polyhedron.     

Existence and sum decomposition of vertex polyhedral convex envelopes

Convex envelopes are a very useful tool in global optimization. However finding the exact convex envelope of a function is a difficult task in general. This task becomes considerably simpler in the case where the domain is a polyhedron and the convex envelope is vertex polyhedral, i.e., has a polyhedral epigraph whose vertices correspond to the vertices of the domain. A further simplification is possible when the convex envelope is sum decomposable, i.e., the convex envelope of a sum of functions coincides with the sum of the convex envelopes of the summands. In this paper we provide characterizations and sufficient conditions for the existence of a vertex polyhedral convex envelope. Our results extend and unify several results previously obtained for special cases of this problem. We then characterize sum decomposability of vertex polyhedral convex envelopes, and we show, among else, that the vertex polyhedral convex envelope of a sum of functions coincides with the sum of the vertex polyhedral convex envelopes of the summands if and only if the latter sum is vertex polyhedral.     

Bounds on the number of vertices of perturbed polyhedra

Finding the incident edges to a degenerate vertex of a polyhedron is a non-trivial problem. So pivoting methods generally involve a perturbation argument to overcome the degeneracy problem. But the perturbation entails a bursting of each degenerate vertex into a cluster of nondegenerate vertices. The aim of this paper is to give some bounds on the number of these perturbed vertices.     

On Simple Polygonalizations with Optimal Area

We discuss the problem of finding a simple polygonalization for a given set of vertices P that has optimal area. We show that these problems are very closely related to problems of optimizing the number of points from a set Q in a simple polygon with vertex set P and prove that it is NP-complete to find a minimum weight polygon or a maximum weight polygon for a given vertex set, resulting in a proof of NP-completeness for the corresponding area optimization problems. This answers a generalization of a question stated by Suri in 1989. Finally, we turn to higher dimensions, where we prove that, for 1 k d , 2 d , it is NP-hard to determine the smallest possible total volume of the k -dimensional faces of a d -dimensional simple nondegenerate polyhedron with a given vertex set, answering a generalization of a question stated by O'Rourke in 1980. Received June 26, 1997, and in revised form February 13, 1999, and May 19, 1999.     

Eulerian detachments with local edge-connectivity

For a graph G, a detachment operation at a vertex transforms the graph into a new graph by splitting the vertex into several vertices in such a way that the original graph can be obtained by contracting all the split vertices into a single vertex. A graph obtained from a given graph G by applying detachment operations at several vertices is called a detachment of graph G. While detachment operations may decrease the connectivity of graphs, there are several works on conditions for preserving the connectivity. In this paper, we present necessary and sufficient conditions for a given graph/digraph to have an Eulerian detachment that satisfies a given local edge-connectivity requirement. We also discuss conditions for the detachment to be loopless.     

Reconstructing orthogonal polyhedra from putative vertex sets

In this paper we study the problem of reconstructing orthogonal polyhedra from a putative vertex set, i.e., we are given a set of points and want to find an orthogonal polyhedron for which this is the set of vertices. This is well-studied in 2D; we mostly focus on 3D, and on the case where the given set of points may be rotated beforehand. We obtain fast algorithms for reconstruction in the case where the answer must be orthogonally convex.     

Reconstructibility of Graphs with a Large Branch: Permutation Group Theory and Graph Reconstruction

Let G be a connected graph having a pendant vertex v such that G-v has pendant vertices in at least two of its branches. Using techniques from permutation group theory, we prove that such a graph G is vertex reconstructible provided it has a branch of large order.     

Local minima of lattices and vertices of Klein polyhedra

We prove that each vertex of a Klein polyhedron of a lattice is a local minimum.     

A Rigidity Criterion for Non-Convex Polyhedra

Let P be a (non-necessarily convex) embedded polyhedron in R³, with its vertices on the boundary of an ellipsoid. Suppose that the interior of $P$ can be decomposed into convex polytopes without adding any vertex. Then P is infinitesimally rigid. More generally, let P be a polyhedron bounding a domain which is the union of polytopes C₁, . . ., C_n with disjoint interiors, whose vertices are the vertices of P. Suppose that there exists an ellipsoid which contains no vertex of P but intersects all the edges of the C_i. Then P is infinitesimally rigid. The proof is based on some geometric properties of hyperideal hyperbolic polyhedra.     

Integral representation and embedding theorems for <Emphasis Type="Italic">n</Emphasis>-dimensional multianisotropic spaces with one anisotropic vertex

We prove embedding theorems for the multianisotropic Sobolev spaces generated by the completely regular Newton polyhedron. Under study is the case of the polyhedron with one anisotropic vertex. We obtain a special integral representation of functions in terms of the tuple of multi-indices of the Newton polyhedron.     

Vertex decomposability and regularity of very well-covered graphs

A graph is called very well-covered if it is unmixed without isolated vertices such that the cardinality of each minimal vertex cover is half the number of vertices. We first prove that a very well-covered graph is Cohen-Macaulay if and only if it is vertex decomposable. Next, we show that the Castelnuovo-Mumford regularity of the quotient ring of the edge ideal of a very well-covered graph is equal to the maximum number of pairwise 3-disjoint edges.     

A solitaire game played on 2-colored graphs

We introduce a solitaire game played on a graph. Initially one disk is placed at each vertex, one face green and the other red, oriented with either color facing up. Each move of the game consists of selecting a vertex whose disk shows green, flipping over the disks at neighboring vertices, and deleting the selected vertex. The game is won if all vertices are eliminated. We derive a simple parity-based necessary condition for winnability of a given game instance. By studying graph operations that construct new graphs from old ones, we obtain broad classes of graphs where this condition also suffices, thus characterizing the winnable games on such graphs. Concerning two familiar (but narrow) classes of graphs, we show that for trees a game is winnable if and only if the number of green vertices is odd, and for n-cubes a game is winnable if and only if the number of green vertices is even and not all vertices have the same color. We provide a linear-time algorithm for deciding winnability for games on maximal outerplanar graphs. We reduce the decision problem for winnability of a game on an arbitrary graph G to winnability of games on its blocks, and to winnability on homeomorphic images of G obtained by contracting edges at 2-valent vertices.     

Circulant tournaments of prime order are tight

We say that a tournament is tight if for every proper 3-coloring of its vertex set there is a directed cyclic triangle whose vertices have different colors. In this paper, we prove that all circulant tournaments with a prime number p≥3 of vertices are tight using results relating to the acyclic disconnection of a digraph and theorems of additive number theory.