论文部分内容阅读
标号问题是图论领域很重要的研究课题之一，本文利用算法与分析中的回溯与分支限界的理论设计程序求解了几类图的标号问题，将计算机构造证明与数学证明相结合研究了两类标号问题：素标号、FFI集。
素标号是由Entringer提出，由Tout,Dabboucy和Howalla给出了树是素图的猜想。目前，经过证明是素图的树有：路径，星图，毛毛虫，完全二叉树，蜘蛛图，橄榄树，所有顶点数小于50的树。其它的具有素标号的图包括：所有的圈，C2k和Cn的分解体，当n是偶数时Wn，完全图Kn(n≥4)，Fans，Helms，Flowers，Stars，K2,n与K3，n(n≠3，7)，Books，Sn(m)，Gn(×)Pm，Pn×K2—(当且仅当n=2或n是奇数)。Vilfred等给出了猜想：当n为素数并且n>m时Pm×Pn为素图，Sundaram等证明了这个猜想而且还证明了当n为素数时，Pn×Pn是素图。Carlson证明了广义的Books和Cn-Snakes图是素图。Yao，Cheng，Zhongfu等人给出了这样的结论：如果一个图的最大的度数至少是n/2(n为顶点数)时，这个图为素图。FFI集是由HarrisKwong，S.M.Lee，HoKuenNg在2006年首次提出的概念，即：{if(G)｜f是图G的Friendly标号}并给出了FFI(Cn)，S.M.Lee等证明了下列图的FI(G)：树，圈，棱柱，M(o)bius梯等。随后WaiCheeShiu，HarrisKwong证明了P2×Pn具有FFI(G)。
鉴于以上问题的研究意义以及广义Petersen图P(n，k)和Kn(o)del图W(3，n)的重要性，本文证明了广义的Petersen图P(n，1)当n≤2500且n是偶数时是素图，以及Kn(o)del图W(3，n)当n≤130且n是偶数时也是素图。本文还给出了广义Petersen图P(n，2)的FFI集。