图的标号研究

Graph labeling problem is a research topic which has practical application background in graph theory. In recent years,domestic and international research in this area is quite active, research results have been applied to radio astronomy, X-ray diffraction crystallography,cryptography, telecommunications network addressing,missile control code design, synchronous machine code design,radio channel allocation and read the DNA sequence. Because it is a NP hard problem, it has an important theoretical significance for solving general NP-hard problem. In this project, we will combine computer construction proof with mathematical proof,develop some better algorithms of searching graph labeling, study the L(2,1)-labeling of cross-hypercube, twisted cube, Mobius cube, augmented cube network and so on in interconnection network topological structure, the gracefulness of the several classes of undirected graphs and digraphs, the antimagic edge labeling of Generalized Petersen Graph, DNA graph and DNA labeling graph problem, and then solve some open problems in these labelings. Based on these research,an efficient way of solving interconnection network graph labeling is explored, which provides theoretical basis for application of interconnection network graph labeling and reference for the solving labeling problem of other graph classes.

图的标号问题是图论中具有实际应用背景的研究课题.近年来，国内外这方面的研究比较活跃，研究成果被广泛应用于射电天文学、X-射线衍射晶体学、密码学、通讯网络编址、导弹控制码设计、同步机码设计、无线电频道分配和读取DNA序列等领域．由于它是NP困难问题，研究它对解决一般的NP困难问题有重要理论意义．本项目将计算机构造和数学证明相结合，研制好的搜索图标号的算法，研究互联网络拓扑结构中各类超立方体变形网络：交叉超立方体、扭立方体、Mobius立方体、增广立方体网络等的L(2,1)-标号问题，几类无向图和有向图的优美性问题，广义Petersen图的反边幻标号问题，DNA图与DNA标号图问题,进而解决这些标号中的一些公开问题．并以此为基础探索出一条解决互联网络拓扑结构图的标号问题的有效途径，为互联网络拓扑结构图的标号的实际应用提供理论基础，也为其他图簇的标号的研究提供借鉴．

课题组主要对图的优美标号、反幻标号、DNA标号、调和标号、图的控制理论、图的诊断度、图的紧性及超图理论等方面的猜想和公开问题进行了研究．课题组利用搜索图的标号的算法，将计算机构造性证明与数学证明相结合，主要研究了有向图n→Cm、→Cn×→Pm(m,n为任意正整数)和→Pa,b的优美性.证明了3→Cm和3→Cm (m是任意正偶数)是优美图. 证明了有向图→Pa,b是优美图当且仅当a和b都是奇数.对广义Petersen图P(n,k)的反幻标号的三个猜想进行了研究，解决了部分猜想. 解决了《中国科学》上关于DNA标号的一个公开问题，即给出了一个图是DNA标号图但不是DNA图的一个特征刻画.对皇冠Qn的调和标号进行研究.证明了从皇冠Qn(2∣n,n≥6)连续去掉三条悬挂边而能保持其调和性；从皇冠Q6连续去掉四条悬挂边而不能保持其调和性；从皇冠Qn(2∣n,n≥8)连续去掉四条悬挂边而能保持其调和性；并猜想：从皇冠Qn(2∣n)最多连续去掉n/2条悬挂边而能保持其调和性.同时对图的符号团边、符号边、逆符号边、符号和反符号边k-等控制数进行了的研究，取得了一些成果，解决了一个有关符号团边控制数的公开问题.对图的g好邻诊断度做了研究. 给出了交错群图网络在PMC模型和MM*模型下的1、2-好邻诊断度. 给出了泡型星图网络在PMC模型和MM*模型下的1-好邻诊断度. 给出了轮图网络在PMC模型和MM*模型下的1-好邻诊断度.对确定一个图是否紧图的问题进行了研究. 从已知的紧图出发构造紧图族的加边法，从而构造了很多紧图族.证明了任意紧图与任意多个孤立点的不交并是紧图；任意紧图的每一个顶点上各增加一条悬挂边的图是紧图.利用这两个结果,从已知紧图可构造出无穷多个紧图族.任意多个完全图的不交并是紧图；圈C3与圈Cn(n>3)的不交并是非紧图；当n(≥3)是奇数时，完全图Kn与图～Kn+1的不交并是非紧图，其中图～Kn+1是从完全图Kn+1删去一因子而得到的图.用边划分方法和圈模型，给出了完全3-一致超图Kn3的5-圈分解和7-圈分解．对王建方界定的圈公理定义下的圈与其它学者定义的圈做了比较研究．以此项目为依托，培养了青年教师和研究生的科研能力，推动了我校图论学科的发展．