zbMATH — the first resource for mathematics

Increasing paths in edge-ordered graphs: the hypercube and random graph. (English) Zbl 1335.05150
Summary: An edge-ordering of a graph \(G=(V,E)\) is a bijection \(\phi:E\to\{1,2,\dots,|E|\}\). Given an edge-ordering, a sequence of edges \(P=e_1,e_2,\dots,e_k\) is an increasing path if it is a path in \(G\) which satisfies \(\phi(e_i)<\phi(e_j)\) for all \(i<j\). For a graph \(G\), let \(f(G)\) be the largest integer \(\ell\) such that every edge-ordering of \(G\) contains an increasing path of length \(\ell\). The parameter \(f(G)\) was first studied for \(G=K_n\) and has subsequently been studied for other families of graphs. This paper gives bounds on \(f\) for the hypercube and the random graph \(G(n,p)\).

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C80 Random graphs (graph-theoretic aspects)
05C35 Extremal problems in graph theory
05C38 Paths and cycles
Full Text: Link