## 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

- Dragoš M. Cvetković, Michael Doob, and Horst Sachs,
*Spectra of graphs*, Pure and Applied Mathematics, vol. 87, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. Theory and application. MR**572262** - Dragoš M. Cvetković and Ivan M. Gutman,
*The algebraic multiplicity of the number zero in the spectrum of a bipartite graph*, Mat. Vesnik**9(24)**(1972), 141–150. MR**323637** - R. L. Graham and H. O. Pollak,
*On embedding graphs in squashed cubes*, Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), Lecture Notes in Math., Vol. 303, Springer, Berlin, 1972, pp. 99–110. MR**0332576** - Frank Harary, Derbiau Hsu, and Zevi Miller,
*The biparticity of a graph*, J. Graph Theory**1**(1977), no. 2, 131–133. MR**444523**, DOI 10.1002/jgt.3190010208 - A. J. Hoffman,
*Eigenvalues and partitionings of the edges of a graph*, Linear Algebra Appl.**5**(1972), 137–146. MR**300937**, DOI 10.1016/0024-3795(72)90023-7
L. Lovász, - G. W. Peck,
*A new proof of a theorem of Graham and Pollak*, Discrete Math.**49**(1984), no. 3, 327–328. MR**743808**, DOI 10.1016/0012-365X(84)90174-2 - Bruce Reznick, Prasoon Tiwari, and Douglas B. West,
*Decomposition of product graphs into complete bipartite subgraphs*, Discrete Math.**57**(1985), no. 1-2, 189–193. MR**816059**, DOI 10.1016/0012-365X(85)90167-0 - H. Tverberg,
*On the decomposition of $K_{n}$ into complete bipartite graphs*, J. Graph Theory**6**(1982), no. 4, 493–494. MR**679606**, DOI 10.1002/jgt.3190060414

*On coverings of graphs*, Theory of Graphs (Proc. Conf. Tihany), Academic Press, 1969, pp. 231-236. —, unpublished.

## 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