Optimal covers with Hamilton cycles in random graphs
Optimal covers with Hamilton cycles in random graphs
复制标题
随机图中汉密尔顿循环的最佳覆盖
作者：
Dan Hefetz;D. Kühn;John Lapinskas;Deryk Osthus
A packing of a graph G with Hamilton cycles is a set of edge-disjoint Hamilton cycles in G. Such packings have been studied intensively and recent results imply that a largest packing of Hamilton cycles in Gn,p a.a.s. has size ⌊δ(Gn,p)/2⌋. Glebov, Krivelevich and Szabó recently initiated research on the ‘dual’ problem, where one asks for a set of Hamilton cycles covering all edges of G. Our main result states that for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tfrac{{log^{117} n}} {n} \leqslant p \leqslant 1 - n^{ - 1/8}$$\end{document}, a.a.s. the edges of Gn,p can be covered by ⌈Δ (Gn,p)/2⌉ Hamilton cycles. This is clearly optimal and improves an approximate result of Glebov, Krivelevich and Szabó, which holds for p ≥ n−1+ɛ. Our proof is based on a result of Knox, Kühn and Osthus on packing Hamilton cycles in pseudorandom graphs.
A packing of a graph G with Hamilton cycles is a set of edge-disjoint Hamilton cycles in G. Such packings have been studied intensively and recent results imply that a largest packing of Hamilton cycles in Gn,p a.a.s. has size ⌊δ(Gn,p)/2⌋. Glebov, Krivelevich and Szabó recently initiated research on the ‘dual’ problem, where one asks for a set of Hamilton cycles covering all edges of G. Our main result states that for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tfrac{{log^{117} n}} {n} \leqslant p \leqslant 1 - n^{ - 1/8}$$\end{document}, a.a.s. the edges of Gn,p can be covered by ⌈Δ (Gn,p)/2⌉ Hamilton cycles. This is clearly optimal and improves an approximate result of Glebov, Krivelevich and Szabó, which holds for p ≥ n−1+ɛ. Our proof is based on a result of Knox, Kühn and Osthus on packing Hamilton cycles in pseudorandom graphs.
关于用哈密尔顿循环覆盖展开图
影响因子：
1
作者：
R. Glebov;M. Krivelevich;T. Szabó
通讯作者：
T. Szabó
随机图的近似哈密尔顿分解
影响因子：
1
作者：
Knox F
通讯作者：
Knox F