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

MaRDI QIDQ281608zbMATH OpenFDO

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

Publication date 11 May 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.03146, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p15

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

zbMATH Keywords

edge-orderinghypercubeincreasing pathrandom graph

Mathematics Subject Classification ID

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

Abstract: An edge-ordering of a graph $G=(V,E)$ is a bijection $phi:Eo1,2,\mathrm{...},|E|$. Given an edge-ordering, a sequence of edges $P=e_1,e_2,\mathrm{...},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)$.

Review text

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

Recommendations

• Increasing Hamiltonian paths in random edge orderings
• Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs
• Monotone paths in dense edge-ordered graphs
• Finding monotone paths in edge-ordered graphs
• Long monotone trails in random edge-labellings of random graphs

Cites work

• Finding monotone paths in edge-ordered graphs
• Increasing Hamiltonian paths in random edge orderings
• Increasing paths in edge ordered graphs
• Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs
• Large monotone paths in graphs with bounded degree
• Monotone paths in edge-ordered sparse graphs
• Optimal Assignments of Numbers to Vertices
• Problems and results in extremal combinatorics. I.
• Some Combinatorial Theorems on Monotonicity
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(8)

• Increasing paths in countable graphs
• Nearly-linear monotone paths in edge-ordered graphs
• Non-crossing monotone paths and binary trees in edge-ordered complete geometric graphs
• Turán problems for edge-ordered graphs
• Increasing Hamiltonian paths in random edge orderings
• Long monotone trails in random edge-labellings of random graphs
• Most edge-orderings of \(K_{n}\) have maximal altitude
• Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q281608)