Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs

Creative Commons License

Kolotoglu E.

JOURNAL OF COMBINATORIAL DESIGNS, vol.21, pp.524-530, 2013 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 21
  • Publication Date: 2013
  • Doi Number: 10.1002/jcd.21335
  • Journal Name: JOURNAL OF COMBINATORIAL DESIGNS
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.524-530
  • Yıldız Technical University Affiliated: No

Abstract

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.