Trees with depression three (Q2470454)

An edge ordering of a graph is an injection \(f\) from the edge set into the set of natural numbers. A simple path for which \(f\) increases along its edge sequence is an \(f\)-ascent, and an \(f\)-ascent is called maximal if it is not contained by a longer \(f\)-ascent. The depression of a graph is the smallest integer \(k\) such that every edge ordering of the graph has a maximal ascent of length at most \(k\). Earlier Cockayne at al. characterized trees with depression 2. This paper characterizes trees with depression 3. The trees with depression 3 are produced by a recursive procedure.