Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs

Creative Commons License

Kolotoglu E.

JOURNAL OF COMBINATORIAL DESIGNS, cilt.21, ss.524-530, 2013 (SCI İndekslerine Giren Dergi) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 21
  • Basım Tarihi: 2013
  • Doi Numarası: 10.1002/jcd.21335
  • Sayfa Sayıları: ss.524-530


A decomposition of a complete graph K-n into disjoint copies of a complete bipartite graph K-s,K- t is called a K-s,K- t-design of order n. The existence problem of K-s,K- t-designs has been completely solved for the graphs K-1,K- k for k >= 1, K-2a,K-2b for a, b >= 1, K-2,K-3 and K-3,K-3. In this paper, I prove that for all s, t >= 1, if there exists a K-s,K- t-design of order N, then there exists a K-s,K- t-design of order n for all n equivalent to N (mod 2st) and n >= N. Giving necessary direct constructions, I provide an almost complete solution for the existence problem for complete bipartite graphs with fewer than 18 edges, leaving five orders in total unsolved. (C) 2012 Wiley Periodicals, Inc.