Combinatorial Curvature



Let G be a (possibly infinite) 2-connected graph embedded on the plane. Suppose that a) each vertex v is of finite degree deg(v) at least 3, and b) each face f is incident with a finite number deg(f) > 3 of edges. Define the combinatorial curvature as the function Psi from vertices to integers as Psi(v) = 1 - (deg(v)/2) + Sum (1/deg(f)) where the sum is taken over all faces f incident with v. For example, in the dodecahedron, the combinatorial curvature at each vertex x is 1 - 3/2 + 3(1/5) = 1/10.

The concept was originally due to Ishida [I]. In [H] Yusuke Higuchi showed that for any infinite planar graph G there exists a positive number epsilon (depending on G), such that if Psi(v) < 0, then Psi (v)  < - epsilon.

Conjecture:  If Sum(Psi(v)) = 2 (where the sum is over all vertices) and Psi(v) > 0 for all vertices, then G is finite.

The conjecture is known to be true for triangulations of maximum degree 5, and dually for cubic graphs whose maximum face is of size 5, but this is not hard. As shown in [H] the problem is related to isoperimetric constants and to the combinatorial Laplacian.

References:

[H] Y. Higuchi, Combinatorial curvature for planar graphs, J. of Graph Theory 38 (2001) 220-229.

[I] M. Ishida, Pseudo-curvature of a graph, in a lecture at the `Workshop on topological graph theory', Yokohama National University, 1990.


Submitted by: Dan Archdeacon (with thanks to Yusuke Higuchi higuchi@cas.showa-u.ac.jp)

Send comments to dan.archdeacon@uvm.edu

November, 2003