A graph theoretical Poincare-Hopf Theorem

Publication date 5 January 2012

Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15)

Abstract: We introduce the index i(v) = 1 - X(S(v)) for critical points of a locally injective function f on the vertex set V of a simple graph G=(V,E). Here S(v) = {w in E | (v,w) in E, f(w)-f(v)<0} is the subgraph of the unit sphere at v in G. It is the exit set of the gradient vector field. We prove that the sum of i(v) over V is always is equal to the Euler characteristic X(G) of the graph G. This is a discrete Poincare-Hopf theorem in a discrete Morse setting. It allows to compute X(G) for large graphs for which other methods become impractical.

This page was built for publication: A graph theoretical Poincare-Hopf Theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6230080)