Geodesic
Increasing paths in edge-ordered graphs: the hypercube and random graph
Jessica De Silva1 ; Theodore Molla2 ; Florian Pfender3 ; Troy Retter4 ; Michael Tait5
1University of Nebraska-Lincoln
2University of Illinois at Urbana-Champaign
3University of Colorado Denver
4Emory University
5University of California, San Diego
The electronic journal of combinatorics, Tome 23 (2016) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

An edge-ordering of a graph $G=(V,E)$ is a bijection $\phi:E\to\{1,2,\ldots,|E|\}$. Given an edge-ordering, a sequence of edges $P=e_1,e_2,\ldots,e_k$ is an increasing path if it is a path in $G$ which satisfies $\phi(e_i)<\phi(e_j)$ for all $i. 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)$.
DOI : 10.37236/5036
Classification : 05C78, 05C80, 05C35, 05C38
Mots-clés : edge-ordering, increasing path, random graph, hypercube

Jessica De Silva  1   ; Theodore Molla  2   ; Florian Pfender  3   ; Troy Retter  4   ; Michael Tait  5

1 University of Nebraska-Lincoln
2 University of Illinois at Urbana-Champaign
3 University of Colorado Denver
4 Emory University
5 University of California, San Diego 
@article{10_37236_5036,
     author = {Jessica De Silva and Theodore Molla and Florian Pfender and Troy Retter and Michael Tait},
     title = {Increasing paths in edge-ordered graphs: the hypercube and random graph},
     journal = {The electronic journal of combinatorics},
     year = {2016},
     volume = {23},
     number = {2},
     doi = {10.37236/5036},
     zbl = {1335.05150},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/5036/}
}
TY  - JOUR
AU  - Jessica De Silva
AU  - Theodore Molla
AU  - Florian Pfender
AU  - Troy Retter
AU  - Michael Tait
TI  - Increasing paths in edge-ordered graphs: the hypercube and random graph
JO  - The electronic journal of combinatorics
PY  - 2016
VL  - 23
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/5036/
DO  - 10.37236/5036
ID  - 10_37236_5036
ER  - 
%0 Journal Article
%A Jessica De Silva
%A Theodore Molla
%A Florian Pfender
%A Troy Retter
%A Michael Tait
%T Increasing paths in edge-ordered graphs: the hypercube and random graph
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/5036/
%R 10.37236/5036
%F 10_37236_5036
Jessica De Silva; Theodore Molla; Florian Pfender; Troy Retter; Michael Tait. Increasing paths in edge-ordered graphs: the hypercube and random graph. The electronic journal of combinatorics, Tome 23 (2016) no. 2. doi: 10.37236/5036

Cité par Sources :