In previous papers the authors showed that almost all d-regular graphs for d greater than or equal to 3 are hamiltonian. In the present paper this result is generalized so that a set of j oriented root edges have been randomly specified for the cycle to contain. The Hamilton cycle must be orientable to agree with all of the orientations on the j root edges. It is shown that the requisite Hamilton cycle almost surely exists if j = o(rootn), and the limiting probability distribution at the threshold j = c rootn is determined when d = 3. It is a corollary (in view of results elsewhere) that almost all claw-free cubic graphs are hamiltonian. There is a variation in which an additional cyclic ordering on the root edges is imposed which must also agree with their ordering on the Hamilton cycle. In this case, the required Hamilton cycle almost surely exists if j = o((n2/5)). The method of analysis is small subgraph conditioning. This gives results on contiguity and the distribution of the number of Hamilton cycles which imply the facts above. (C) 2001 John Wiley & Sons, Inc. [References: 15]
展开▼
机译:在先前的论文中,作者表明d等于或大于3的几乎所有d-正则图都是汉密尔顿图。在本论文中,此结果是广义的,因此已随机指定了一组j方向的根边缘以包含该循环。汉密尔顿循环必须是可定向的,以与j个根边缘上的所有定向一致。结果表明,如果j = o(rootn)几乎必然存在必要的汉密尔顿循环,并且在d = 3时确定阈值j = c rootn的极限概率分布。这是必然的(考虑其他地方的结果)几乎所有无爪立方图都是汉密尔顿图。存在一种变体,其中在根边缘上施加了附加的循环排序,该循环排序也必须与其在汉密尔顿循环上的排序一致。在这种情况下,如果j = o((n2 / 5)),则几乎必然存在所需的汉密尔顿循环。分析方法是小的子图条件。这给出了连续性和汉密尔顿循环数分布的结果,这暗示了上述事实。 (C)2001 John Wiley&Sons,Inc. [参考:15]
展开▼