Degree monotone paths and graph operations

Abstract

A path P in a graph G is said to be a degree monotone path if the sequence of degrees of the vertices of P in the order in which they appear on P is monotonic. The length of the longest degree monotone path in G is denoted by mp(G). This parameter was first studied in an earlier paper by the authors where bounds in terms of other parameters of G were obtained. In this paper we concentrate on the study of how mp(G) changes under various operations on G. We first consider how mp(G) changes when an edge is deleted, added, contracted or subdivided. We similarly consider the effects of adding or deleting a vertex. We sometimes restrict our attention to particular classes of graphs. Finally we study mp(G × H) in terms of mp(G) and mp(H) where × is either the Cartesian product or the join of two graphs. In all these cases we give bounds on the parameter mp of the modified graph in terms of the original graph or graphs and we show that all the bounds are sharp