Ryan McCullogh (Binghamton)

Conservation, Potentials, and the Postman Structure of Graphs

Abstract for the Combinatorics Seminar
2010 December 13

A notion of "conservativeness", defined for graphs with integrally weighted edges, leads to significant new understanding of the Chinese Postman Problem. A weighted graph is conservative if the sum of weights around every cycle is non-negative. (This is different from the normal definition of conservation.) A potential is a vertex function that upholds the edge weights in a certain sense. The talk will explain these concepts and present some results about them, all from a paper of Andras Sebo.


To the Combinatorics Seminar Web page.