Eigensharp graphs:Decomposition into complete bipartite subgraphs

Thomas Kratzke, Bruce Reznick, Douglas West

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)637-653
Number of pages17
JournalTransactions of the American Mathematical Society
Volume308
Issue number2
DOIs
StatePublished - Aug 1988

ASJC Scopus subject areas

  • Mathematics(all)
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Eigensharp graphs:Decomposition into complete bipartite subgraphs'. Together they form a unique fingerprint.

Cite this