Eigensharp graphs: decomposition into complete bipartite subgraphs
Authors:
Thomas Kratzke, Bruce Reznick and Douglas West
Journal:
Trans. Amer. Math. Soc. 308 (1988), 637653
MSC:
Primary 05C50
MathSciNet review:
929670
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Let be the minimum number of complete bipartite subgraphs needed to partition the edges of , and let be the larger of the number of positive and number of negative eigenvalues of . It is known that ; graphs with are called eigensharp. Eigensharp graphs include graphs, trees, cycles with or , prisms with , "twisted prisms" (also called "Möbius ladders") with or , 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 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.
 [1]
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 YorkLondon, 1980. Theory and application. MR 572262
(81i:05054)
 [2]
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 0323637
(48 #1993)
 [3]
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), Springer, Berlin, 1972,
pp. 99–110. Lecture Notes in Math., Vol. 303. MR 0332576
(48 #10902)
 [4]
Frank
Harary, Derbiau
Hsu, and Zevi
Miller, The biparticity of a graph, J. Graph Theory
1 (1977), no. 2, 131–133. MR 0444523
(56 #2874)
 [5]
A.
J. Hoffman, Eigenvalues and partitionings of the edges of a
graph, Linear Algebra and Appl. 5 (1972),
137–146. MR 0300937
(46 #97)
 [6]
L. Lovász, On coverings of graphs, Theory of Graphs (Proc. Conf. Tihany), Academic Press, 1969, pp. 231236.
 [7]
, unpublished.
 [8]
G.
W. Peck, A new proof of a theorem of Graham and Pollak,
Discrete Math. 49 (1984), no. 3, 327–328. MR 743808
(85i:05201), http://dx.doi.org/10.1016/0012365X(84)901742
 [9]
Bruce
Reznick, Prasoon
Tiwari, and Douglas
B. West, Decomposition of product graphs into complete bipartite
subgraphs, Discrete Math. 57 (1985), no. 12,
189–193. MR
816059 (87i:05157), http://dx.doi.org/10.1016/0012365X(85)901670
 [10]
H.
Tverberg, On the decomposition of 𝐾_{𝑛} into
complete bipartite graphs, J. Graph Theory 6 (1982),
no. 4, 493–494. MR 679606
(83m:05111), http://dx.doi.org/10.1002/jgt.3190060414
 [1]
 D. M. Cvetković, M. Doob, and H. Sachs, Spectra of graphs, Academic Press, New York, 1979. MR 572262 (81i:05054)
 [2]
 D. M. Cvetković and I. Gutman, The algebraic multiplicity of the number zero in the spectrum of a bipartite graph, Mat. Vesnik 9 (1972), 141150. MR 0323637 (48:1993)
 [3]
 R. L. Graham and H. O. Pollak, On embedding graphs in squashed cubes, Graph Theory and Applications (Proc. 2nd Internat. Conf. Graph Theory, Kalamazoo 1972), Lecture Notes in Math., vol. 303, SpringerVerlag, 1973, pp. 99110. MR 0332576 (48:10902)
 [4]
 F. Harary, D. F. Hsu, and Z. Miller, The biparticity of a graph, J. Graph Theory 1 (1977), 131133. MR 0444523 (56:2874)
 [5]
 A. J. Hoffman, Eigenvalues and partitionings of the edges of a graph, Linear Algebra Appl. 5 (1972), 137146. MR 0300937 (46:97)
 [6]
 L. Lovász, On coverings of graphs, Theory of Graphs (Proc. Conf. Tihany), Academic Press, 1969, pp. 231236.
 [7]
 , unpublished.
 [8]
 G. W. Peck, A new proof of a theorem of Graham and Pollak, Discrete Math. 49 (1984), 327328. MR 743808 (85i:05201)
 [9]
 B. Reznick, P. Tiwari, and D. B. West, Decomposition of product graphs into complete bipartite subgraphs, Discrete Math. 57 (1985), 179183. MR 816059 (87i:05157)
 [10]
 H. Tverberg, On the decomposition of into complete bipartite subgraphs, J. Graph Theory 6 (1982), 493494. MR 679606 (83m:05111)
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC:
05C50
Retrieve articles in all journals
with MSC:
05C50
Additional Information
DOI:
http://dx.doi.org/10.1090/S00029947198809296705
PII:
S 00029947(1988)09296705
Keywords:
Decomposition,
bipartite subgraph,
graph product
Article copyright:
© Copyright 1988
American Mathematical Society
