| 基于矩阵直积的膨胀图构造 |
| |
| 引用本文： | 吴占斌,许道云. 基于矩阵直积的膨胀图构造[J]. 贵州大学学报(自然科学版), 2007, 24(5): 445-449 |
| |
| 作者姓名： | 吴占斌 许道云 |
| |
| 作者单位： | 贵州大学计算机科学与技术学院,贵州,贵阳,550025;贵州大学计算机科学与技术学院,贵州,贵阳,550025 |
| |
| 基金项目： | 贵州省自然科学基金项目(黔科合J字[2007]2003号) |
| |
| 摘 要： | 将矩阵直积的概念引入图论,证明了直积图的结点数、度及特征值分别等于原图结点数之积、度之积和特征值之积,并将这些性质应用于由两个膨胀图构造一个新的膨胀图,分别从矩阵的角度和图的角度给出了构造算法。
|
| 关 键 词： | 正则图 直积 膨胀图 |
| 文章编号： | 1000-5269（2007）05-0445-05 |
| 修稿时间： | 2007-07-05 |
Expander Graphs' Construction Based on Kronecker Product |
| |
| WU Zhan-bin,XU Dao-yun. Expander Graphs' Construction Based on Kronecker Product[J]. Journal of Guizhou University(Natural Science), 2007, 24(5): 445-449 |
| |
| Authors: | WU Zhan-bin XU Dao-yun |
| |
| Affiliation: | Department of Computer Science, Guizhou University, Guiyang 550025 ,China |
| |
| Abstract: | The concept of Kronecker product is introduced into graph theory in this paper.And the relevant conclusions are proved.For example,the product graph's vertex number,degree and eigenvalues is equal to the product of the counterparts of the original graphs respectively.These properties are used to construct a new expander graph with two known expander graphs.The construction is shown both in matrix and graph method,which are described in the algorithms. |
| |
| Keywords: | regular graph Kronecker product expander graph |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
