کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650086 | 1342473 | 2009 | 5 صفحه PDF | دانلود رایگان |

An edge ordering of a graph G=(V,E)G=(V,E) is an injection f:E→Q+f:E→Q+ where Q+Q+ is the set of positive rational numbers. A (simple) path λλ for which ff increases along its edge sequence is an ff-ascent, and a maximal ff-ascent if it is not contained in a longer ff-ascent. The depression ε(G)ε(G) of GG is the least integer kk such that every edge ordering of GG has a maximal ascent of length at most kk.It has been shown in [E.J. Cockayne, G. Geldenhuys, P.J.P. Grobler, C.M. Mynhardt, J. van Vuuren, The depression of a graph, Utilitas Math. 69 (2006) 143–160] that the difference diam(L(G))−ε(G) may be made arbitrarily large. We prove that the difference ε(G)−diam(L(G)) can also be arbitrarily large, thus answering a question raised in [E.J. Cockayne, G. Geldenhuys, P.J.P. Grobler, C.M. Mynhardt, J. van Vuuren, The depression of a graph, Utilitas Math. 69 (2006) 143–160].
Journal: Discrete Mathematics - Volume 309, Issue 6, 6 April 2009, Pages 1774–1778