Increasing Paths in Edge-Ordered Graphs: The Hypercube and Random Graph
Jessica De Silva, Theodore Molla, Florian Pfender, Troy Retter, Michael B. Tait · The Electronic Journal of Combinatorics · 2016
An edge-ordering of a graph $G=(V,E)$ is a bijection $\phi:E\to\{1,2,\ldots,|E|\}$. Given an edge-ordering, a sequence of edges $P=e_1,e_2,\ldots,e_k$ is an increasing path if it is a path in $G$ which satisfies $\phi(e_i)<\phi(e_j)$ for all $i