The depression of a graph and the diameter of its line graph |
| |
Authors: | Iris Gaber-Rosenblum |
| |
Institution: | The Academic College of Tel-Aviv-Yaffo, Tel-Aviv, Israel |
| |
Abstract: | An edge ordering of a graph G=(V,E) is an injection f:E→Q+ where Q+ is the set of positive rational numbers. A (simple) path λ for which f increases along its edge sequence is an f-ascent, and a maximal f-ascent if it is not contained in a longer f-ascent. The depression ε(G) of G is the least integer k such that every edge ordering of G has a maximal ascent of length at most k.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 may be made arbitrarily large. We prove that the difference 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]. |
| |
Keywords: | Edge ordering Increasing path Monotone path Depression |
本文献已被 ScienceDirect 等数据库收录! |
|