Concerning the complexity of deciding isomorphism of block designs

Marlene J. Colbourn, Charles J. Colbourn

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


A construction is described to encode an arbitrary graph uniquely as a block design. This demonstrates that describing whether two block designs (without repeated blocks) are isomorphic is polynomial time equivalent to solving graph isomorphism. This result supplies evidence for the claim that isomorphism testing for block designs is a hard subcase of graph isomorphism.

Original languageEnglish (US)
Pages (from-to)155-162
Number of pages8
JournalDiscrete Applied Mathematics
Issue number3
StatePublished - Jul 1981
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Concerning the complexity of deciding isomorphism of block designs'. Together they form a unique fingerprint.

Cite this