彩色Ore定理  

A Rainbow Version of Ore Theorem

作　　者：高立青 王健 GAO Liqing;WANG Jian(School of Economics and Management,Taiyuan University of Technology,Taiyuan 030024,China;School of Economics and Management,University of Electronic Science and Technology of China,Chengdu 611731,China;School of Mathematics,Taiyuan University of Technology,Taiyuan 030024,China)

机构地区：[1]太原理工大学经济管理学院,山西太原030024 [2]电子科技大学经济与管理学院,四川成都611731 [3]太原理工大学数学学院,山西太原030024

出　　处：《运筹与管理》2023年第10期108-113,共6页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(72004154)。

摘　　要：设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)中每个图的边数都大于等于((n-1)/2)+2,则{G_(1),G_(2),…,G_(n)}中包含一个彩色哈密尔顿圈。进一步地,如果G_(1),G_(2),…,G_(n-1)中每个图的边数都大于等于((n-1)/2)+1,则{G_(1),G_(2),…,G_(n-1)}中包含一条彩色哈密尔顿路。Let G_(1),G_(2),…,G_(n) be n graphs on the same vertex set V with|V|=n.If C is a cycle of length n such that each edge belongs to a different graph,then we call C a rainbow Hamilton cycle on{G_(1),G_(2),…,G_(n)}.Similarly,if P is a path of length n-1 such that each edge belongs to a different graph of G_(1),G_(2),…,G_(n-1),then we call P a rainbow Hamilt on path on{G_(1),G_(2),…,G_(n-1)}.Recently,Joos and Kim have proved a rainbow version of Dirac theorem,i.e.,if each of G_(1),G_(2),…,G_(n) has minimum degree at least n/2,then{G_(1),G_(2),…,G_(n)}contains a rainbow Hamilton cycle.In this paper,by the shifting method we show that if each of G_(1),G_(2),…,G_(n) has at least ((n-1)/2)+2 edges,then{G_(1),G_(2),…,G_(n)}contains a rainbow Hamilton cycle.Moreover,if each of G_(1),G_(2),…,G_(n-1) has at least (n-1)/2)+1 edges,then{G_(1),G_(2),…,G_(n-1)}contains a rainbow Hamilton path.The shifting operator is a powerful tool in extremal set theory,which was invented by Erd s,Ko and Rado and further developed by Frankl.The shifting operator can be applied to graphs and hypergraphs and preserve the number of edges.It is well known that the shifting operator cannot increase the matching number of graphs and hypergraphs.In the present paper,we show that if a graph system{G_(1),G_(2),…,G_(n)}does not contain a rainbow Hamilton cycle,then one can apply the shifting operator to G_(1),G_(2),…,G_(n) simultaneously without producing a rainbow Hamilton cycle.By applying the shifting operator to G_(1),G_(2),…,G_(n) repeatedly,eventually we shall obtain a sequence of shifted graphs G_(1),G_(2),…,G_(n).For two pairs(x_(1),x_(2))and(y_(1),y_(2)),define the shifted partial order as:(x_(1),x_(2))(y_(1),y_(2))if and only if either x_(1) y_(1) and x_(2) y_(2) or x_(1) y_(2) and x_(2) y_(1) hold.The shifted graphs have the following nice property:if x_(1)x_(2) is an edge of G and G_(i)s shifted,then for any pair(x_(1),x_(2))(y_(1),y_(2)),y_(1)y_(2) is also an edge of G.Let H n,a,b be a graph with the vertex set{1

关 键 词：Ore定理 彩色哈密尔顿圈 彩色哈密尔顿路 

分 类 号：O157.5[理学—数学]