图的标号研究

项目名称： 图的标号研究

项目编号： No.61262018

项目类型： 地区科学基金项目

立项/批准年度： 2013

项目学科： 自动化技术、计算机技术

项目作者： 吉日木图

作者单位： 内蒙古民族大学

项目金额： 47万元

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

中文关键词： 图的标号；图的控制；图的诊断度；图的紧性；

英文摘要： 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 ot

英文关键词： lableing of graph；domination of graph；diagnosability of graph；compactness of graph；