New Graphs with Thinly Spread Positive Combinatorial Curvature

Abstract

The combinatorial curvature at a vertex v of a plane graph G is defi ned as KG(v) = 1-v/2+ ∑_(f~v)1/|f|. As a consequence of Euler's formula, the total curvature of a plane graph is 2. In 2008, Zhang showed that |V(G)| < 580 for plane graphs with everywhere positive combinatorial curvature other than prisms and antiprisms. We improve on the largest known such graph (on 138 vertices) found by Réti, Bitay, and Kosztolányi in 2005 by giving a graph on 208 vertices having positive combinatorial curvature at every vertex with KG(v)∈{1/13, 1/66, 1/132, 1/858} for all v ∈ V(G). We also give a non-orientable PCC graph with 104 vertices.