Menu
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 \( \operatorname{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 \( \operatorname{mp}(G) \) changes under various operations on \( G \). We first consider how \( \operatorname{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 \( \operatorname{mp}(G \times H) \) in terms of \( \operatorname{mp}(G) \) and \( \operatorname{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 \( \operatorname{mp} \) of the modified graph in terms of the original graph or graphs and we show that all the bounds are sharp.