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 monotonically non-decreasing. The length of the longest degree monotone path in $G$ is denoted by $\mathrm{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 $\mathrm{mp}(G)$ changes under various operations on $G$. We first consider how $\mathrm{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 $\mathrm{mp}(G\times H)$ in terms of $\mathrm{mp}(G)$ and $\mathrm{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 $\mathrm{mp}$ of the modified graph in terms of the original graph or graphs and we show that all the bounds are sharp.