# 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
##### Keywords:
edge-ordering; increasing path; random graph; hypercube
Full Text: