Computing the metric dimension of convex polytopes generated by wheel related graphs

An ordered set \({W = \{w_1, . . . ,w_k\} \subseteqq V (G)}\) of vertices of G is called a resolving set or locating set for G if every vertex is uniquely determined by its vector of distances to the vertices in W. A resolving set of minimum cardinality is called a metric basis for G and this cardinality is the metric dimension or location number of G, denoted by \({\beta(G)}\).     

Complete intersection toric ideals of oriented graphs and chorded-theta subgraphs

Let G=(V,E) be a finite, simple graph. We consider for each oriented graph $G_{\mathcal{O}}$ associated to an orientation ${\mathcal{O}}$ of the edges of G, the toric ideal $P_{G_{\mathcal{O}}}$ . In this paper we study those graphs with the property that $P_{G_{\mathcal{O}}}$ is a binomial complete intersection, for all ${\mathcal{O}}$ . These graphs are called $\text{CI}{\mathcal{O}}$ graphs. We prove that these graphs can be constructed recursively as clique-sums of cycles and/or complete graphs. We introduce chorded-theta subgraphs and some of their properties. Also we establish that the $\text{CI}{\mathcal{O}}$ graphs are determined by the property that each chorded-theta has a transversal triangle. Finally we explicitly give the minimal forbidden induced subgraphs that characterize these graphs, these families of forbidden graphs are: prisms, pyramids, thetas and a particular family of wheels that we call θ-partial wheels.     

Indecomposable convex polytopes

Shephard has given a criterion for the indecomposability (in the sense of Minkowski addition) of a convex polytope, in terms of strong chains of indecomposable faces joining pairs of vertices. Here, this criterion is weakened, to one involving strongly connected sets of indecomposable faces meeting every facet.     

Note dual polytopes of rational convex polytopes

LetP ^d be a rational convex polytope with dimP=d such that the origin of ^d is contained in the interiorP – P ofP. In this paper, from a viewpoint of enumeration of certain rational points inP (which originated in Ehrhart's work), a necessary and sufficient condition for the dual polytopeP ^dual ofP to be integral is presented.This research was performed while the author was staying at Massachusetts Institute of Technology during the 1988–89 academic year.     

Diagonals of convex polytopes

Translated from Matematicheskie Zametki, Vol. 49, No. 4, pp. 20–30, April, 1991.     

On empty convex polytopes

Letn andd be integers,n>d 2. We examine the smallest integerg(n,d) such that any setS of at leastg(n,d) points, in general position in E^d, containsn points which are the vertices of an empty convexd-polytopeP, that is, SintP = 0. In particular we show thatg(d+k, d) = d+2k–1 for 1 k iLd/2rL+1.     

Mixing regular convex polytopes

The mixing operation for abstract polytopes gives a natural way to construct a minimal common cover of two polytopes. In this paper, we apply this construction to the regular convex polytopes, determining when the mix is again a polytope, and completely determining the structure of the mix in each case.     

Nondegenerate families of convex cones and convex polytopes

This paper describes relations between convex polytopes and certain families of convex cones in R ⁿ .The purpose is to use known properties of convex cones in order to solve Helly type problems for convex sets in R ⁿ or for spherically convex sets in S _n , the n-dimensional unit sphere. These results are strongly related to Gale diagrams.     

Colorful polytopes and graphs

The paper investigates connections between abstract polytopes and properly edge colored graphs. Given any finite n-edge-colored n-regular graph G, we associate to G a simple abstract polytope P _G of rank n, the colorful polytope of G, with 1-skeleton isomorphic to G. We investigate the interplay between the geometric, combinatorial, or algebraic properties of the polytope P _G and the combinatorial or algebraic structure of the underlying graph G, focussing in particular on aspects of symmetry. Several such families of colorful polytopes are studied including examples derived from a Cayley graph, in particular the graphicahedra, as well as the flagadjacency polytopes and related monodromy polytopes associated with a given abstract polytope. The duals of certain families of colorful polytopes have been important in the topological study of colored triangulations and crystallization of manifolds.     

Semisymmetric graphs from polytopes

Every finite, self-dual, regular (or chiral) 4-polytope of type {3,q,3} has a trivalent 3-transitive (or 2-transitive) medial layer graph. Here, by dropping self-duality, we obtain a construction for semisymmetric trivalent graphs (which are edge- but not vertex-transitive). In particular, the Gray graph arises as the medial layer graph of a certain universal locally toroidal regular 4-polytope.     

Characterizing subgraphs of Hamming graphs

Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E(G) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u, υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005     

Pancyclic subgraphs of random graphs

An n‐vertex graph is called pancyclic if it contains a cycle of length t for all 3≤t≤n. In this article, we study pancyclicity of random graphs in the context of resilience, and prove that if p>n^?1/2, then the random graph G(n, p) a.a.s. satisfies the following property: Every Hamiltonian subgraph of G(n, p) with more than edges is pancyclic. This result is best possible in two ways. First, the range of p is asymptotically tight; second, the proportion of edges cannot be reduced. Our theorem extends a classical theorem of Bondy, and is closely related to a recent work of Krivelevich et al. The proof uses a recent result of Schacht (also independently obtained by Conlon and Gowers). © 2011 Wiley Periodicals, Inc.     

Barycentric coordinates for convex polytopes

An extension of the standard barycentric coordinate functions for simplices to arbitrary convex polytopes is described. The key to this extension is the construction, for a given convex polytope, of a unique polynomial associated with that polytope. This polynomial, theadjoint of the polytope, generalizes a previous two-dimensional construction described by Wachspress. The barycentric coordinate functions for the polytope are rational combinations of adjoints of various dual cones associated with the polytope.     

Complete subgraphs are elusive

We would like to decide whether a graph with a given vertex set has a certain property. We do this by probing the pairs of vertices one by one, i.e., asking whether a given pair of vertices is an edge or not. At each stage we make full use of the information we have up to that point. If there is an algorithm (a sequence of probes depending on the previous information) that allows us to come to a decision before checking every pair, the property is said to be incomplete, otherwise it is called complete or elusive. We show that the property of containing a complete subgraph with a given number of vertices is elusive. The proof also implies that the property of being r-chromatic (r fixed) is elusive.     

Unavoidable subgraphs of colored graphs

A natural generalization of graph Ramsey theory is the study of unavoidable sub-graphs in large colored graphs. In this paper, we find a minimal family of unavoidable graphs in two-edge-colored graphs. Namely, for a positive even integer k, let S_k be the family of two-edge-colored graphs on k vertices such that one of the colors forms either two disjoint K_k/2's or simply one K_k/2. Bollobás conjectured that for all k and ε>0, there exists an n(k,ε) such that if n?n(k,ε) then every two-edge-coloring of K_n, in which the density of each color is at least ε, contains a member of this family. We solve this conjecture and present a series of results bounding n(k,ε) for different ranges of ε. In particular, if ε is sufficiently close to , the gap between our upper and lower bounds for n(k,ε) is smaller than those for the classical Ramsey number R(k,k).     

Spanning subgraphs of random graphs

We propose a problem concerning the determination of the threshold function for the edge probability that guarantees, almost surely, the existence of various sparse spanning subgraphs in random graphs. We prove some bounds and demonstrate them in the cases of ad-cube and a two dimensional lattice.