超立方体线图的谱相关性质的研究

Research on the Properties of Spectrum on the Line Graph of Hypercube

摘要: 超立方体Q_n及其变体作为许多大型处理机系统的一种常用网络拓扑结构，是迄今为止最为重要和最具吸引力的网络拓扑结构之一。一个简单图G的线图line(G)是以图G的边集作为其顶点集，两个顶点之间有一条边当且仅当这两个点对应的边在原图G中是相邻的。1993年张福基等人利用超立方体的邻接多项式给出了超立方体的线图的邻接多项式的具体表达式。时隔近30年，随着图论的发展和兴起衍生出很多新的工具，本文从图的无符号拉普拉斯矩阵与其线图的邻接矩阵关系的角度出发，进一步研究超立方体的线图的一些性质，如：更为简化的超立方体线图的邻接多项式、邻接谱、生成树的个数以及超立方体线图的二部图的判定等。

Abstract: The hypercube Q_n coupled with their variants is used to construct various common network topology models for many large processor systems, hypercube network is one of the most essential and inviting network topological structures today. The line graph line(G) of simple graph G is a graph with vertex set E(G) and there is an edge between two vertices if and only if the edges corresponding to these two points are adjacent in graph G. In 1993 Zhang Fuji et al. gave the specific adjacent polynomial of the line graph of the hypercube. After nearly 30 years, with the development of graph theory, a series of new tools are derived. In this paper, starting from the perspective of the relation of the unsigned Laplacian matrix of the graph and its adjacency matrix of the line graph, we further study some properties of the line graph of the hypercube, such as the more simplified adjacency polynomial, the number of spanning trees, and the determination of the bipartite graph of the line graph of hypercube.