论文标题
超越主要差异图的汉密尔顿性
Beyond Hamiltonicity of Prime Difference Graphs
论文作者
论文摘要
图形是哈密顿量，如果它包含一个循环，该循环完全访问图形的每个顶点一次。在本文中，我们考虑了图$ g_n $的hamiltonicity问题，该问题称为$ n $的质量差异图，带有顶点$ \ {1,2，\ cdots，n \} $，而edge set $ \ {uv：| u-v：| u-v：| u-v | $是prime数字$ \} $。最近的结果是由Sun提出的，后来由Chen证明，他断言$ G_N $是Hamiltonian，hamiltonian售价为5美元。本文将其结果扩展到三个方向。首先，我们证明，对于任何两个整数$ a $和$ b $，带有$ 1 \ leq a <b \ leq n $，除了某些小$ n $外，$ g_n $的汉密尔顿路径$ g_n $从$ a $到$ b $。该结果意味着素数差异图的Hamiltonity属性的鲁棒性，从某种意义上说，对于$ g_n $中的任何边缘$ e $，都有一个包含$ e $的汉密尔顿周期。其次，我们表明，主要差异图所包含的循环结构比哈密顿量多得多。确切地说，对于任何整数$ n \ geq 7 $，Prime差异图$ g_n $包含订单$ n $的完整图的任何2因子作为子图。最后，我们发现$ g_n $可能包含更多的边缘汉密尔顿周期。特别是，这些汉密尔顿周期是由两个主要差异产生的。
A graph is Hamiltonian if it contains a cycle which visits every vertex of the graph exactly once. In this paper, we consider the problem of Hamiltonicity of a graph $G_n$, which will be called the prime difference graph of order $n$, with vertex set $\{1,2,\cdots, n\}$ and edge set $\{uv: |u-v|$ is a prime number$\}$. A recent result, conjectured by Sun and later proved by Chen, asserts that $G_n$ is Hamiltonian for $n\geq 5$. This paper extends their result in three directions. First, we prove that for any two integers $a$ and $b$ with $1\leq a<b\leq n$, there is a Hamilton path in $G_n$ from $a$ to $b$ except some cases of small $n$. This result implies robustness of the Hamiltonicity property of the prime difference graph in a sense that for any edge $e$ in $G_n$ there exists a Hamilton cycle containing $e$. Second, we show that the prime difference graph contains considerably more about the cycle structure than Hamiltonicity; precisely, for any integer $n\geq 7$, the prime difference graph $G_n$ contains any 2-factor of the complete graph of order $n$ as a subgraph. Finally, we find that $G_n$ may contain more edge-disjoint Hamilton cycles. In particular, these Hamilton cycles are generated by two prime differences.
