Geodesic
On the existence of Hamilton cycles with a periodic pattern in a random digraph
Alan Frieze1 ; Xavier Pérez-Giménez2 ; Paweł Prałat3
1Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA, USA
2Department of Mathematics, University of Nebraska-Lincoln, Lincoln NE, USA
3Department of Mathematics Ryerson University
The electronic journal of combinatorics, Tome 27 (2020) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We consider Hamilton cycles in the random digraph $D_{n,m}$ where the orientation of edges follows a pattern other than the trivial orientation in which the edges are oriented in the same direction as we traverse the cycle. We show that if the orientation forms a periodic pattern, other than the trivial pattern, then approximately half the usual $n\log n$ edges are needed to guarantee the existence of such Hamilton cycles a.a.s.
DOI : 10.37236/9376
Classification : 05C80, 05C45, 05C20
Mots-clés : random digraph process, alternating pattern

Alan Frieze  1   ; Xavier Pérez-Giménez  2   ; Paweł Prałat  3

1 Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA, USA
2 Department of Mathematics, University of Nebraska-Lincoln, Lincoln NE, USA
3 Department of Mathematics Ryerson University 
@article{10_37236_9376,
     author = {Alan Frieze and Xavier P\'erez-Gim\'enez and Pawe{\l} Pra{\l}at},
     title = {On the existence of {Hamilton} cycles with a periodic pattern in a random digraph},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {4},
     doi = {10.37236/9376},
     zbl = {1453.05120},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9376/}
}
TY  - JOUR
AU  - Alan Frieze
AU  - Xavier Pérez-Giménez
AU  - Paweł Prałat
TI  - On the existence of Hamilton cycles with a periodic pattern in a random digraph
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9376/
DO  - 10.37236/9376
ID  - 10_37236_9376
ER  - 
%0 Journal Article
%A Alan Frieze
%A Xavier Pérez-Giménez
%A Paweł Prałat
%T On the existence of Hamilton cycles with a periodic pattern in a random digraph
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/9376/
%R 10.37236/9376
%F 10_37236_9376
Alan Frieze; Xavier Pérez-Giménez; Paweł Prałat. On the existence of Hamilton cycles with a periodic pattern in a random digraph. The electronic journal of combinatorics, Tome 27 (2020) no. 4. doi: 10.37236/9376

Cité par Sources :