Article ID Journal Published Year Pages File Type
4650782 Discrete Mathematics 2008 10 Pages PDF
Abstract

An edge ordering of a graph G=(V,E)G=(V,E) is an injection f:E→Nf:E→N. 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 of G is the least integer k such that every edge ordering of G has a maximal ascent of length at most k. We characterise trees with depression three.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,