Decomposing complete graphs into Kr×Kc's

Hung-Lin Fu, F. K. Hwang, M. Jimbo, Yukiyasu Mutoh*, C. L. Shiue

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

We consider the problem of decomposing a complete graph into the Cartesian product of two complete graphs Kr and Kc. This problem originated from the clone library screening. We give a general method of constructing such decompositions using various sorts of combinatorial designs. In particular, for r=3 and c=3, we show that such a decomposition exists for all n satisfying some simple necessary conditions.

Original languageEnglish
Pages (from-to)225-236
Number of pages12
JournalJournal of Statistical Planning and Inference
Volume119
Issue number2
DOIs
StatePublished - 1 Feb 2004

Keywords

  • Graph decomposition and grid-blocks
  • Grid-block designs

Fingerprint Dive into the research topics of 'Decomposing complete graphs into K<sub>r</sub>×K<sub>c</sub>'s'. Together they form a unique fingerprint.

Cite this