×

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)\).

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