网络拓扑的超能整循环图构造

Construction of hyperenergetic integral circulant graphs for network topology

循环图是一类重要的网络拓扑结构图,在并行计算和分布计算中发挥重要作用。图G的能量E(G)定义为图的特征值的绝对值之和。具有n个顶点的图G称为超能图如果图G的能量E(G)>2n-2。一个图称为循环图,若它是循环群上的Cayley图,即它的邻接矩阵是一个循环矩阵;整循环图是指循环图的特征值全为整数。借助Ramanujans和,利用Euler函数和Mobius函数,讨论了整循环图的超能性。利用Cartesian积图给出了一个构造超能整循环图的方法。

Circulant graphs are an important class of interconnection networks in parallel and distributed computing. The energy E（G） of a graph G is the sum of the absolute values of the eigenvalues of G. A graph G with n vertices is said to be＂hyperenergetic＂if E（G） 〉2n- 2. A graph is called circulant if it is Cayley graph on the circulant group, i.e.its adjacency matrix is circulant. A graph is called integral if all eigenvalues of its adjacency matrix are integers. According to Ramanujans sum, using Euler function and the Mobius function, this paper studies the properties of hyperenergetic of integral circulant graphs. Using the Cartesian product of two graphs, it also constructs hyperenergetic integral circulant graphs.