Packing Hamilton cycles online

DOI10.1017/S0963548318000159MaRDI QIDQ3177359zbMATH OpenOpenAlexFDO

Authors Joseph Briggs, Michael Krivelevich, Po-Shen Loh, Alan Frieze, Benny Sudakov

Publication date 24 July 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

\(\sigma\) edge-disjoint Hamilton cycles

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Eulerian and Hamiltonian graphs (05C45) Random graphs (graph-theoretic aspects) (05C80)

Abstract: It is known that w.h.p. the hitting time $a{u}_{2sigma}$ for the random graph process to have minimum degree $2sigma$ coincides with the hitting time for $sigma$ edge disjoint Hamilton cycles. In this paper we prove an online version of this property. We show that, for a fixed integer $sigmageq2$, if random edges of $K_n$ are presented one by one then w.h.p. it is possible to color the edges online with $sigma$ colors so that at time $a{u}_{2sigma}$, each color class is Hamiltonian.

Recommendations

• Packing directed Hamilton cycles online
• On the Number of Hamilton Cycles in Sparse Random Graphs
• Optimal packings of Hamilton cycles in sparse random graphs
• On the number of hamilton cycles in a random graph
• Hamiltonicity thresholds in Achlioptas processes

Cites work

• Dependent random choice
• Edge-disjoint Hamilton cycles in random graphs
• Getting a directed Hamilton cycle two times faster
• Hamiltonian circuits in random graphs
• Hamiltonicity thresholds in Achlioptas processes
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 3922707 (Why is no real title available?)
• scientific article; zbMATH DE number 3950585 (Why is no real title available?)
• scientific article; zbMATH DE number 3549021 (Why is no real title available?)
• Introduction to Random Graphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• On the strength of connectedness of a random graph
• Optimal packings of Hamilton cycles in sparse random graphs
• Probability Inequalities for Sums of Bounded Random Variables

Cited in

(5)

• Hamiltonicity thresholds in Achlioptas processes
• Packing directed Hamilton cycles online
• scientific article; zbMATH DE number 19173 (Why is no real title available?)
• Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs
• Fast construction on a restricted budget

This page was built for publication: Packing Hamilton cycles online

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