亚循环网络及网络上的编码

Graphs are the topology structures of networks. The combinatorial properties of networks, including connectivity, diameter, etc. play an important role in analysing of network performance. Codes from graphs are getting more and more attention. In this project, a new network, called metacirculant networks, will be studied, including the characterization of their underlying graphs, the combinatorial properties of these networks and codes related. Some important metacirculant graphs will be characterized which is a hot topic in algebraic graph theory. This will provide important mathematical tools for the study of the other two problems as well. The outcome of codes and combinatorial properties of networks will give main parameters of codes and networks, some new codes and networks with good properties would be constructed as byproducts. Combining the methods in algebraic graph theory, graph theory, network theory and coding theory, this project would represent an important research direction for these four fields.

图是网络的拓扑结构。而网络的组合性质包括连通度、直径等在研究网络性能中起到了重要的作用。网络上的编码问题也受到了越来越多的关注。本项目将研究一种新的网络：亚循环网络。主要研究该网络的拓扑结构、组合性质以及相关的编码问题。网络结构的研究将给出一些重要的亚循环图的刻画，这不但是代数图论的一个热点问题，同时也会为网络组合性质和编码的研究提供重要的数学基础。网络组合性质以及编码的研究将给出一些重要的网络或码的参数，并有望构造出新的具有良好性质的网络和编码。本项目将代数图论、图论、网络和编码四个方向有机的结合起来进行研究，为这四个方向的研究提供了新的方法和思路。

图是网络的拓扑结构。网络的拓扑结构在网络参数的分析中起了非常重要的作用。循环图是一类非常重要的网络结构。在过去的几十年里，由于循环图具有最优的容错性和路由容量，循环图被广泛的应用于计算机设计和电信网络的设计中。大多数早期的研究集中在使用循环图来构建分布式和并行系统的互连网络。 现在循环图在计算机科学、图论和离散数学等学科中都得到了深入研究。考虑到循环图是一类十分特殊的图，本项目旨在将循环网络推广到更一般的网络：亚循环网络。随着信息技术的发展，信息传递已经与我们的生活密不可分。编码理论则在这一过程中提供了数学基础。因此本项目拟从网络的拓扑结构性质的、组合性质以及网络上的编码三个方面对亚循环网络进行一个系统的研究。主要包括以下几个方面：1. 亚循环网络的结构分析。对亚循环图的几个图类进行了研究，给出了四度亚循环图的同构分类，并将该方法推广到更一般的情形，分析了度数与点数互素的亚循环图的拓扑结构; 2. 点传递自补图的研究。我们在研究中，给出了仿射型点传递自补图的一般性构造，并给出了几类新的自补Cayley图; 3. 对一些图类的拉普拉斯谱、距离能量等参数进行了研究，确定了这些图类能够达到最大和最小距离拉普拉斯谱的图；给出了一些图类的距离矩阵的行列式的惯性和公式，并应用该结论，确定了该图类中所有具有最大（或最小）D能量的图；4. 对亚循环网络中的定位码、识别码和自识别码进行了研究，确定了这三类码在几个重要图类中的最小阶数，并分别构造了具有最小阶数的码；对几个重要的图类中的完美码进行了研究，给出了各类图中一个码为完美码的充要条件。