Increasing paths in edge-ordered graphs: the hypercube and random graph

Abstract: An edge-ordering of a graph

G = (V, E)

is a bijection

p h i : E o 1, 2, ..., | E |

. Given an edge-ordering, a sequence of edges

P = e_{1}, e_{2}, ..., e_{k}

is an increasing path if it is a path in

G

which satisfies

p h i (e_{i}) < p h i (e_{j})

for all

i < j

. For a graph

G

, let

f (G)

be the largest integer

e l l

such that every edge-ordering of

G

contains an increasing path of length

e l l

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

.

Full work available at URL: https://arxiv.org/abs/1502.03146

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cites Work

Cited In (8)

This page was built for publication: Increasing paths in edge-ordered graphs: the hypercube and random graph