Increasing paths in edge-ordered graphs: the hypercube and random graph. (English) Zbl 1335.05150

De Silva, Jessica; Molla, Theodore; Pfender, Florian; Retter, Troy; Tait, Michael

Electron. J. Comb. 23, No. 2, Research Paper P2.15, 9 p. (2016).

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

Keywords:

edge-ordering; increasing path; random graph; hypercube