论文标题
覆盖树木图的汉密尔顿
Hamiltonicity of covering graphs of trees
论文作者
论文摘要
在本文中，我们考虑通过在每个顶点上抬起一棵树作为循环基团上的电压图来覆盖图形。我们概括了一种地狱，nishiyama和Stacho的工具，被称为台球战略，用于在路径的覆盖图中构建汉密尔顿周期。我们表明，我们的扩展工具可用于为覆盖与Batagelj和Pisanski以及Hell，Nishiyama和Stacho相似的树木图的大麻提供新的条件。接下来，我们专门关注从循环组上的电压图$ \ mathbb z_p $ p $ $ p $ $ \ mathbb z_p $。我们证明，对于给定的反身树$ t $，其边缘标签是从有限套件中随机分配的，相应的升降机几乎是哈密顿式的，对于足够大的Prime订购的循环组$ \ MATHBB ZP $。最后，我们表明，如果将反身树$ t $提升到一个大质量订单的组$ \ mathbb z_p $上，那么对于$ t $ $ t $的边缘的任何非零元素的任何分配，$ t $的相应封面的边缘都有很大的周长。
In this paper, we consider covering graphs obtained by lifting a tree with a loop at each vertex as a voltage graph over a cyclic group. We generalize a tool of Hell, Nishiyama, and Stacho, known as the billiard strategy, for constructing Hamiltonian cycles in the covering graphs of paths. We show that our extended tool can be used to provide new sufficient conditions for the Hamiltonicity of covering graphs of trees that are similar to those of Batagelj and Pisanski and of Hell, Nishiyama, and Stacho. Next, we focus specifically on covering graphs obtained from trees lifted as voltage graphs over cyclic groups $\mathbb Z_p$ of large prime order $p$. We prove that for a given reflexive tree $T$ whose edge labels are assigned uniformly at random from a finite set, the corresponding lift is almost surely Hamiltonian for a large enough prime-ordered cyclic group $\mathbb Z_p$. Finally, we show that if a reflexive tree $T$ is lifted over a group $\mathbb Z_p$ of a large prime order, then for any assignment of nonzero elements of $\mathbb Z_p$ to the edges of $T$, the corresponding cover of $T$ has a large circumference.
