论文标题
沉重而轻的路径和汉密尔顿周期
Heavy and Light Paths and Hamilton Cycles
论文作者
论文摘要
给定图形$ g $，我们用$ f（g，u_0，k）$表示$ g $的长度$ k $的路径数量从$ u_0 $开始。在最高学位3的图表中，带有$ exp（1）$的边缘权重$ i.i.d. $，我们提供了一个简单的证据，表明（假设$ f（g，u_0，k）=ω（1）$）至少从$ u_0 $开始的长度$ k $的最大$ k $的预期重量至少从$ u_0 $开始 \ begin {align*} （1-o（1））\ left（k+\ frac {\ log_2 \ left（f（g，u_0，k）\ right）} {2} \ right）， \ end {align*} 从$ u_0 $开始 \ begin {align*} （1+O（1））\ left（k- \ frac {\ log_2 \ left（f（g，u_0，k）\ right）} {2} \ right）。 \ end {align*} 我们证明了这种结果对汉密尔顿路径和汉密尔顿周期的直接含义，在随机图中，我们表明通常存在这种重量的路径和周期。最后，我们讨论了该结果与超临界$ g（n，p）$的巨大组成部分中最长周期的问题的联系。
Given a graph $G$, we denote by $f(G,u_0,k)$ the number of paths of length $k$ in $G$ starting from $u_0$. In graphs of maximum degree 3, with edge weights $i.i.d.$ with $exp(1)$, we provide a simple proof showing that (under the assumption that $f(G,u_0,k)=ω(1)$) the expected weight of the heaviest path of length $k$ in $G$ starting from $u_0$ is at least \begin{align*} (1-o(1))\left(k+\frac{\log_2\left(f(G,u_0,k)\right)}{2}\right), \end{align*} and the expected weight of the lightest path of length $k$ in $G$ starting from $u_0$ is at most \begin{align*} (1+o(1))\left(k-\frac{\log_2\left(f(G,u_0,k)\right)}{2}\right). \end{align*} We demonstrate the immediate implication of this result for Hamilton paths and Hamilton cycles in random cubic graphs, where we show that typically there exist paths and cycles of such weight as well. Finally, we discuss the connection of this result to the question of a longest cycle in the giant component of supercritical $G(n,p)$.
