Eigensharp graphs: decomposition into complete bipartite subgraphs
Eigensharp graphs: decomposition into complete bipartite subgraphs
复制标题
DOI：
10.1090/s0002-9947-1988-0929670-5
复制
发表时间：
1988-02
影响因子：
1.3
通讯作者：
T. M. Kratzke;B. Reznick;D. West
中科院分区：
文献类型：
--
作者：
T. M. Kratzke;B. Reznick;D. West
设r（G）是划分G的边所需的最小完全二部子图个数，r（G）是G的正特征值个数和负特征值个数中的较大者.已知r（G）> r（G），满足r（G）= r（G）的图称为特征尖图.特征夏普图包括图、树、n = 4或n 54 4k的圈Cn、n 54 3k的棱柱CnOK2、n = 3或n 54 3k的“扭曲棱柱”（也称为“莫比乌斯梯”）Mn以及圈的某些笛卡尔积。在一定条件下，特征尖图的弱（Kronecker）积是特征尖图.例如，具有相同数量的正负特征值的特征夏普图类在弱积下是封闭的。如果有限弱积中的每个图都是eigensharp的，没有零特征值，并且分解为r（G）星，则积是eigensharp的。最后一个结果中的假设可以被削弱。最后，并不是所有的eigensharp图的弱积都是eigensharp的。
Let r(G) be the minimum number of complete bipartite subgraphs needed to partition the edges of G, and let r(G) be the larger of the number of positive and number of negative eigenvalues of G. It is known that r(G) > r(G); graphs with r(G) = r(G) are called eigensharp. Eigensharp graphs include graphs, trees, cycles Cn with n = 4 or n 54 4k, prisms CnOK2 with n 54 3k, "twisted prisms" (also called "Mobius ladders") Mn with n = 3 or n 54 3k, and some Cartesian products of cycles. Under some conditions, the weak (Kronecker) product of eigensharp graphs is eigensharp. For example, the class of eigensharp graphs with the same number of positive and negative eigenvalues is closed under weak products. If each graph in a finite weak product is eigensharp, has no zero eigenvalues, and has a decomposition into r(G) stars, then the product is eigensharp. The hypotheses in this last result can be weakened. Finally, not all weak products of eigensharp graphs are eigensharp.