Almost self-complementary factors of complete bipartite graphs

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

A complete bipartite graph without one edge, K̃n, m, is called almost complete bipartite graph. A graph K̃2n+1, 2m+1 that can be decomposed into two isomorphic factors with a given diameter d is called d-isodecomposable. We prove that K̃2n+1, 2m+1 is d-isodecomposable only if d = 3, 4, 5, 6 or ∞ and completely determine all d-isodecomposable almost complete bipartite graphs for each diameter. For d = ∞ we, moreover, present all classes of possible disconnected factors.

Original languageEnglish (US)
Pages (from-to)317-327
Number of pages11
JournalDiscrete Mathematics
Volume167-168
DOIs
StatePublished - Apr 15 1997

Keywords

  • Graph decompositions
  • Isomorphic factors
  • Self-complementary graphs

Fingerprint Dive into the research topics of 'Almost self-complementary factors of complete bipartite graphs'. Together they form a unique fingerprint.

Cite this