24
$\begingroup$

One can define the Euler characteristic χ for a graph as the number of vertices minus the number of edges. Thus an $n$-cycle has $\chi = 0$ and $K_4$ has $\chi=-2$. Is there an analog for the Gauss-Bonnet theorem for graphs, something akin to:

     [total turn angle] $+$ [enclosed curvature] $= \tau + \omega = 2 \pi \chi$ ?

Certainly if one embeds the graph on a manifold, then an interpretation is possible via Gauss-Bonnet on the manifold. But is there a more purely combinatorial interpretation?

Addendum. (27Nov11). A new paper on this topic just appeared on the arXiv: Oliver Knill (who answered below back in March), "A graph theoretical Gauss-Bonnet-Chern Theorem." arXiv:1111.5395v1. Here is Knill's first figure:
     Knill Fig 1

$\endgroup$
3
  • 1
    $\begingroup$ When you say "embeds the graph in a manifold", do you mean "embeds the graph in a compact surface so that its complement is a disjoint union of disks"? I am having trouble seeing how this would work in a more general situation. $\endgroup$
    – S. Carnahan
    May 28, 2010 at 14:49
  • $\begingroup$ Yes, that is what I meant, your precision is much preferable to my off-hand way of expressing it. $\endgroup$ May 28, 2010 at 15:09
  • $\begingroup$ @Joseph: Are you explicitly interested in general graphs - including trees or the graph shown above - or is it OK to consider specific families of graphs, e.g. polyhedral graphs? (I believe that it is possible to have a purely combinatorial interpretation of Gauss-Bonnet for polyhedral graphs, independent of a specific embedding.) $\endgroup$ Jan 22, 2013 at 15:37

3 Answers 3

19
$\begingroup$

One can do the following : given a graph with $n$ vertices and $m$ edges, define the scalar curvature of a vertex $x$ of valency $v(x)$ by $S(x)=2-v(x)$. Isolated and pendant vertices have positive scalar curvature, $S$ vanishes precisely on degree two vertices (wich are those one want to call flat), and is negative for higher degrees, reminiscent of the trees being $\mathrm{CAT}(-\infty)$.

Now $\sum_x S(x)=2n-\sum_x v(x)=2\chi$ is a Gauss-bonnet formula. It is very simple, but one does not expects much more from such local considerations.

I guess that to get a more subtle formula, one can try to add some geometric structure to the graph (for example, a length on each edge and an angle for each pair of adjacent edges, and maybe a circular ordering of the edges incident to each vertex).

$\endgroup$
3
  • $\begingroup$ Very nice! Thanks! Presumably, then, there is a version for, say, a simple cycle in the graph enclosing a certain amount of "scalar curvature." $\endgroup$ May 28, 2010 at 14:51
  • 1
    $\begingroup$ I like this answer! Intuitively a negative curvature point is one with 'more space than one might expect around it' and a positive curvature point is one with less. Ties up quite nicely I think... $\endgroup$ May 28, 2010 at 15:55
  • 3
    $\begingroup$ It's probably worth mentioning that $S(x) = 2-v(x)$ is the Euler characteristic of a tubular neighborhood of the vertex $x$, if you take any embedding of the graph in 3-space (i.e. a sphere for $v(x) = 0$, a pair of pants for $v(x) = 3$). By usual Gauss-Bonnet, this is equal to the total curvature of this neighborhood-surface up to a constant, and summing over all vertices gives the curvature of the tubular neighborhood of the whole graph, a closed orientable surface of genus $1-\chi(G)$. $\endgroup$ Mar 22, 2017 at 11:55
9
$\begingroup$

There is indeed a version of Gauss-Bonnet for graphs $G$ embedded on a 2-manifold. Here, the combinatorial curvature at a vertex $x$ of $G$ is

$1-\frac{deg(x)}{2} + \sum_{f \sim v} \frac{1}{size(f)}$,

where $f \sim v$ means that the face $f$ is incident to the vertex $x$.

This paper by Chen and Chen, then gives a Gauss-Bonnet formula for embedded infinite graphs with a finite number of accumulation points.

$\endgroup$
6
$\begingroup$

There are different type of curvatures for graphs. In two dimensions its not the degree of the point which matters but the length of the circles at the point like in differential geometry. This is different from the degree if graphs with boundary are considered. The simplest curvature for two dimensional graphs (I defined the dimension for graphs in http://arxiv.org/abs/1009.2292). For the curvature K(x) = 6-|S(x)|, any two dimensional graph G has total curvature 6 chi(G). More interesting and subtle is a second order curvature 2|S1(x)|-|S2(x)| which is differential geometrically motivated because curvature is a second order difference notion. Gauss-Bonnet is now not true in general and it seems that some smoothness condition needs to be satisfied. It is true for all two dimensional graphs non-negative curvature and for graphs which are "smooth" enough in some sense which I still struggle to define. I myself got more interested in Gauss-Bonnet-Chern for n-dimensional graphs and have a result there. There is a natural Chern-Euler form on n-dimensional graphs those total sum is the Euler characteristic for an n-dimensional graph. This form is defined also in odd dimensions but seems to be zero (it is in 3 dimensions but I still struggle to verify this in higher dimensions). Note that all this is purely graph theoretical. No additional structure on the graph is necessary. No embedding in an ambient Euclidean space necessary for example. The inductive dimension as defined in the above mentioned paper (revised here: http://www.math.harvard.edu/~knill/graphgeometry/papers/1.pdf) is a natural way to define polyhedra and polytopes as graphs which become n-dimensional graphs after some truncation or stellation procedure. The inductive dimension for graphs looks similar to inductive dimension usually considered in topology but is utterly different. With the usual inductive dimension, any graph would be one dimensional.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.