Oscillation of graphs

Abstract

The oscillation of a graph G is the largest integer t such that for all linear orders f of its edges, G has a (simple) path P of length t for which f alternately increases and decreases along the edge sequence of P. Various results concerning graphs with small oscillation are established. For example we characterize graphs with oscillation at least three and deduce the oscillation of any tree. Open questions are included.