-
彩色Ore定理
- 高立青, 王健
-
2023, 32(10):
108-113.
DOI: 10.12005/orms.2023.0327
-
摘要
(
)
PDF (1009KB)
(
)
-
参考文献 |
相关文章 |
计量指标
设G1,G2,···,Gn是在同样的顶点集合V上的n个图,且满足|V|=n。设C是包含V中所有顶点的一个圈,如果C的边集合是从G1,G2,···,Gn中每个图选择一条边得到的,则称C为{G1,G2,···,Gn}上的一个彩色哈密尔顿圈。设P是包含V中所有顶点的一条路,如果P中每条边均来自G1,G2,···,Gn-1中不同的图,那么称P为{G1,G2,···,Gn-1}上的一个彩色哈密尔顿路。最近,Joos和Kim证明了彩色的Dirac定理, 即如果G1,G2,···,Gn中每个图的最小度都大于等于n/2,则{G1,G2,···,Gn}中包含一个彩色哈密尔顿圈。在本文中,我们采用移位方法证明了如果G1,G2,···,Gn中每个图的边数都大于等于$\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+2$,则{G1,G2,···,Gn}中包含一个彩色哈密尔顿圈。进一步地,如果G1,G2,···,Gn-1中每个图的边数都大于等于$\left(\begin{array}{c} n-1 \\ 2 \end{array}\right)+1$,则{G1,G2,···,Gn-1}中包含一条彩色哈密尔顿路。