Degree monotone paths

Abstract

We shall study degree-monotone paths in graphs, a problem inspired by the celebrated theorem of Erdos-Szekeres concerning the longest monotone subsequence of a given sequence of numbers. A path P in a graph G is said to be a degree monotone path if the sequence of degrees of the vertices in P in the order they appear in P is monotonic. In this paper we shall consider these three problems related to this parameter. We first find bounds on mp(G) in terms of other parameters of G. We then study f(n, k) defined to be the maximum number of edges in a graph on n vertices with mp(G) < k. Finally we estimate the minimum and the maximum over all graphs G on a n vertices of mp(G) + mp(G).