TY - JOUR
T1 - Decomposition of product graphs into complete bipartite subgraphs
AU - Reznick, Bruce
AU - Tiwari, Prasoon
AU - West, Douglas B.
N1 - Funding Information:
by the National Science Foundation and a fellowship from the Alfred P. Sloan
PY - 1985/11
Y1 - 1985/11
N2 - Let τ(G) be the minimum number of complete bipartite subgraphs needed to partition the edges of G. Let Gn be the weak product of cliques, Kn1x...xKn1. This graph has vertices {x:0≤xii}, with edges between those vectors that differ in each coordinate. Theorem: τ(Gn) = ∑Π |S|eveniε{lunate}S (ni-1).
AB - Let τ(G) be the minimum number of complete bipartite subgraphs needed to partition the edges of G. Let Gn be the weak product of cliques, Kn1x...xKn1. This graph has vertices {x:0≤xii}, with edges between those vectors that differ in each coordinate. Theorem: τ(Gn) = ∑Π |S|eveniε{lunate}S (ni-1).
UR - http://www.scopus.com/inward/record.url?scp=50849148393&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=50849148393&partnerID=8YFLogxK
U2 - 10.1016/0012-365X(85)90167-0
DO - 10.1016/0012-365X(85)90167-0
M3 - Article
AN - SCOPUS:50849148393
SN - 0012-365X
VL - 57
SP - 189
EP - 193
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 1-2
ER -