New Graphs with Thinly Spread Positive Combinatorial Curvature

From NZJM

Jump to: navigation, search

New Zealand Journal of Mathematics

Vol. 41, (2011), Pages 39-43


Ruanui Nicholson

Department of Mathematics

The University of Auckland

Auckland, New Zealand

mailto:rnic052@aucklanduni.ac.nz

Jamie Sneddon

Department of Mathematics

The University of Auckland

Auckland, New Zealand

mailto:j.sneddon@auckland.ac.nz




Abstract The combinatorial curvature at a vertex v of a plane graph G is defined as K_G(v) = 1 - v/2 + \sum_{f \sim 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 K_G(v) \in \left\{1/13,1/66,1/132,1/858\right\} for all v \in V(G). We also give a non-orientable PCC graph with 104 vertices.

Keywords positive combinatorial curvature, planar graph.

Classification (MSC2000) Primary 05C10; Secondary 52B05.

Full text

Full paper

Personal tools