标题
  • 标题
  • 作者
  • 关键词

彩色Ore定理

2023-10-25分类号:O157.5

【作者】高立青   王健
【部门】太原理工大学经济管理学院  电子科技大学经济与管理学院  太原理工大学数学学院  
【摘要】设G_1,G_2,…,G_n是在同样的顶点集合V上的n个图,且满足|V|=n。设C是包含V中所有顶点的一个圈,如果C的边集合是从G_1,G_2,…,G_n中每个图选择一条边得到的,则称C为{G_1,G_2,…,G_n}上的一个彩色哈密尔顿圈。设P是包含V中所有顶点的一条路,如果P中每条边均来自G_1,G_2,…,G_(n-1)中不同的图,那么称P为{G_1,G_2,…,G_(n-1)}上的一个彩色哈密尔顿路。最近,Joos和Kim证明了彩色的Dirac定理,即如果G_1,G_2,…,G_n中每个图的最小度都大于等于n/2,则{G_1,G_2,…,G_n}中包含一个彩色哈密尔顿圈。在本文中,我们采用移位方法证明了如果G_1,G_2,…,G_n中每个图的边数都大于等于■,则{G_1,G_2,…,G_n}中包含一个彩色哈密尔顿圈。进一步地,如果G_1,G_2,…,G_(n-1)中每个图的边数都大于等于■,则{G_1,G_2,…,G_(n-1)}中包含一条彩色哈密尔顿路。
【关键词】Ore定理  彩色哈密尔顿圈  彩色哈密尔顿路
【基金】国家自然科学基金资助项目(72004154)
【所属期刊栏目】运筹与管理
文献传递