网格图的零指标的研究（英文）

ON THE NULLITY OF GRID GRAPHS

一个图的零指标是指该图的邻接矩阵的零特征值的个数.二部图的可以应用到化学中,用来检验分子的稳定性.在本文中,我们对网格图标进行了研究,找到了此图类中关于零指标的一个递归关系.借助此任何一个网格图(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.