Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Eigensharp graphs: decomposition into complete bipartite subgraphs
HTML articles powered by AMS MathViewer

by Thomas Kratzke, Bruce Reznick and Douglas West PDF
Trans. Amer. Math. Soc. 308 (1988), 637-653 Request permission

Abstract:

Let $\tau (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 $\tau (G) \geqslant r(G)$; graphs with $\tau (G) = r(G)$ are called eigensharp. Eigensharp graphs include graphs, trees, cycles ${C_n}$ with $n = 4$ or $n \ne 4k$, prisms ${C_n}\square {K_2}$ with $n \ne 3k$, "twisted prisms" (also called "Möbius ladders") ${M_n}$ with $n = 3$ or $n \ne 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 $\tau (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.
References
Similar Articles
  • Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C50
  • Retrieve articles in all journals with MSC: 05C50
Additional Information
  • © Copyright 1988 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 308 (1988), 637-653
  • MSC: Primary 05C50
  • DOI: https://doi.org/10.1090/S0002-9947-1988-0929670-5
  • MathSciNet review: 929670