图的标号问题与计算机无线网络代码分配问题

Nowadays, the rapid growth of computer wireless networks highlighted the scarcity of avail-able codes for communication with minimum interference, then it is more and more important to optimize the finite codes. Different from former distance-two labeling which arosed from frequency assignment problem, graph distance-two labeling in this project arosed from code assignment in computer network, and the difference between the labels of distance-two vertices must be not less than the difference between the labels of adjacent vertices. Hence, the results related to the frequency assignment problem cannot be used to the code assignment problem, hence, we need to focus on studying the graph labeling related to code assignment. Since the product graphs and Cactus graph are the most important graphs to represent the computer network, then this project will study two different problems: One, distance-two labelings and circular coloring of product graphs and Cactus graphs related to the code assignment. After that, we will work on the (circular) distance-two labelings of general graphs. Two, we will apply the results to the real wirless network of computer and optimize the code assignment.

当今世界，随着计算机无线网络的日益发展，对于代码的需求日益增加，对有限的代码进行最优分配显得越来越重要。不同于频道分配问题概括出来的图的距离二标号问题，计算机无线网络的代码分配问题要求距离二站点的代码差异比相邻点要大，因此，基于频道分配问题的图的各类距离二标号问题的研究成果并极少适用于代码分配问题，因此，基于代码分配问题的图的标号问题必须专门研究。目前，乘积图和Cactus图则是通信工程相关学者刻画网络分布的两类最重要的图，因此，本项目主要展开两方面的研究：一方面，针对基于代码分配问题的乘积图和Cactus图的距离二标号问题以及图的圆着色问题展开研究，并在基础上，研究一般图的距离二（圆）标号问题；另一方面，将所得研究成果应用到代码分配问题中去，利用相关性质，确定对应的图模拟不同类型的实际无线网络问题，并利用图的标号问题的相关结论提供优化方案。

图的标号问题是当前图论和组合数学共同关注的一个重要且传统的研究课题，它具有重要的理论意义和广泛的应用价值。当今世界，随着计算机无线网络的日益发展，对于代码的需求日益增加，对有限的代码进行最优分配显得越来越重要。不同于频道分配问题概括出来的图的距离二标号问题，计算机无线网络的代码分配问题要求距离二站点的代码差异比相邻点要大，因此，基于频道分配问题的图的各类距离二标号问题的研究成果并不完全适用于代码分配问题。因乘积图、Cactus图、广义彼得森图等是刻画网络分布的几类最重要的图，因此，本课题对基于计算机无线网络的代码分配问题的乘积图、Cactus图、广义彼得森图、平方图等的距离二标号问题以及圆标号问题展开了研究。目前，我们主要确定了任意长度平方路和圈、Cactus图、几类广义彼得森图、任意路和圈的强乘积图的L(j,k)-标号数以及路和圈的笛卡尔乘积图，任意长度平方路的L(j,k)-圆标号数，这里的j不大于k且为任意实数。另外，在研究过程中，我们利用了Maple对标号进行了分析，得到了相关问题的一般性结论。并且，把图形的相关性质与标号结论应用到了环形珠垫编织以及图的绘制等相关问题中，所有的研究成果以论文的形式发表或接收共11篇。