摘要
一个图的零指标是指该图的邻接矩阵的零特征值的个数.二部图的可以应用到化学中,用来检验分子的稳定性.在本文中,我们对网格图标进行了研究,找到了此图类中关于零指标的一个递归关系.借助此任何一个网格图(P_m×P_n)的零指标可以在O(log_2n)时间内计算出来.
Let G be a graph and let A（G） be the adjacency matrix of G. The nullity of a graph G, denoted by η（G）, is the multiplicity of the eigenvalue zero in the spectrum of G. The nullities of bipartite graphs are applied to chemistry for testing instability of molecules. In this paper, we find a recursive relation on the nullity of grid graphs. Therefore, for a grid graph Pn ×Pm, η（Pn × Pro） could be determined in O（log2 n） time.
出处
《南京大学学报（数学半年刊）》
2017年第1期61-75,共15页
Journal of Nanjing University(Mathematical Biquarterly)
基金
partially supported by National Natural Science Foundation of China(Nos.11301538 and 11571096)
关键词
图谱
零指标
邻接矩阵
网格图
spectrum, humility, adjacent matrix, grid graph
