TY - JOUR

T1 - Eigensharp graphs:Decomposition into complete bipartite subgraphs

AU - Kratzke, Thomas

AU - Reznick, Bruce

AU - West, Douglas

PY - 1988/8

Y1 - 1988/8

N2 - 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 (Formula Presented) graphs with (Formula Presented) are called eigensharp. Eigensharp graphs include graphs, trees, cycles Cn with n = 4 or n 4k, prisms CnÜÄ2 with n 3k, “twisted prisms” (also called “Möbius ladders”) Mn with n = 3 or 3A:, 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.

AB - 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 (Formula Presented) graphs with (Formula Presented) are called eigensharp. Eigensharp graphs include graphs, trees, cycles Cn with n = 4 or n 4k, prisms CnÜÄ2 with n 3k, “twisted prisms” (also called “Möbius ladders”) Mn with n = 3 or 3A:, 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.

UR - http://www.scopus.com/inward/record.url?scp=0037686957&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0037686957&partnerID=8YFLogxK

U2 - 10.1090/S0002-9947-1988-0929670-5

DO - 10.1090/S0002-9947-1988-0929670-5

M3 - Article

AN - SCOPUS:0037686957

VL - 308

SP - 637

EP - 653

JO - Transactions of the American Mathematical Society

JF - Transactions of the American Mathematical Society

SN - 0002-9947

IS - 2

ER -