Graphs whose adjacency matrices have rank equal to the number of distinct nonzero rows
Graphs whose adjacency matrices have rank equal to the number of distinct nonzero rows
复制标题
DOI：
10.1016/j.laa.2012.06.027
复制
发表时间：
2013-05
影响因子：
1.1
通讯作者：
Liang-Hao Huang;B. Tam;Shu-hui Wu
中科院分区：
文献类型：
--
作者：
Liang-Hao Huang;B. Tam;Shu-hui Wu
对于简单图G，令rank(G)和dnzr(G)分别表示G的邻接矩阵A(G)的秩和不同非零行的数量。给出两个顶点不相交图G1,G2的连接G1∨G2的等效条件，以满足rank(G1∨G2)=dnzr(G1∨G2)。为图G的已知关系rank(G)=dnzr(G)提供了新的证明。我们的方法依赖于邻域等价类、简化图和简化邻接矩阵的概念，还依赖于将图的邻接矩阵的频谱与其简化邻接矩阵的频谱相关联的已知结果，以及特殊2×2块形式的实对称矩阵的非奇异性的新表征。我们的处理提供了构造除 cographs 之外的图 G 的方法，满足rank(G)=dnzr(G)。作为附带结果，我们还表明每个有理数都等于连通非奇异图的邻接矩阵的逆矩阵的条目之和。
For a simple graph G, let rank(G) and dnzr(G) denote respectively the rank and the number of distinct nonzero rows of the adjacency matrix A(G) of G. Equivalent conditions are given for the join G1∨G2of two vertex-disjoint graphs G1,G2to satisfy rank(G1∨G2)=dnzr(G1∨G2). A new proof is provided for the known relation rank(G)=dnzr(G) for cographs G. Our approach relies on the concepts of neighborhood equivalence classes, reduced graph and reduced adjacency matrix, and also on a known result that relates the spectrum of the adjacency matrix of a graph with that of its reduced adjacency matrix as well as a new characterization of the nonsingularity of a real symmetric matrix in a special 2×2 block form. Our treatment provides ways to construct graphs G, other than cographs, that satisfy rank(G)=dnzr(G). As a side result we also show that every rational number is equal to the sum of the entries of the inverse of the adjacency matrix of a connected nonsingular graph.