Degree Monotone Paths and Graph Operations

Yair Caro, Josef Lauri, Christina Zarb

Published 2014-08-14Version 1

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 \times H)$ in terms of $mp(G)$ and $mp(H)$ where $\times$ 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.