Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/112264
Title: | Degree monotone paths and graph operations |
Authors: | Caro, Yair Lauri, Josef Zarb, Christina |
Keywords: | Graph theory Graphic methods Mathematics -- Charts, diagrams, etc. |
Issue Date: | 2016 |
Publisher: | Charles Babbage Research Centre |
Citation: | Caro, Y., Lauri, J., & Zarb, C. (2016). Degree monotone paths and graph operations. Journal of Combinatorial Mathematics and Combinatorial Computing, 99, 151-166. |
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 |
URI: | https://www.um.edu.mt/library/oar/handle/123456789/112264 |
Appears in Collections: | Scholarly Works - FacSciMat |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Degree_monotone_paths_and_graph_operations_2016.pdf | 285.21 kB | Adobe PDF | View/Open |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.