Decomposition of product graphs into complete bipartite subgraphs

Bruce Reznick, Prasoon Tiwari, Douglas B. West

Research output: Contribution to journalArticlepeer-review


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≤xi<ni}, with edges between those vectors that differ in each coordinate. Theorem: τ(Gn) = ∑Π |S|eveniε{lunate}S (ni-1).

Original languageEnglish (US)
Pages (from-to)189-193
Number of pages5
JournalDiscrete Mathematics
Issue number1-2
StatePublished - Nov 1985

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


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

Cite this