Premium
Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs
Author(s) -
Kolotoğlu Emre
Publication year - 2013
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21335
Subject(s) - mathematics , combinatorics , bipartite graph , cograph , robertson–seymour theorem , complete bipartite graph , discrete mathematics , disjoint sets , modular decomposition , 1 planar graph , pathwidth , graph , chordal graph , line graph
A decomposition of a complete graph K n into disjoint copies of a complete bipartite graph K s , tis called a K s , t ‐design of order n . The existence problem of K s , t ‐designs has been completely solved for the graphs K 1 , kfor k ≥ 1 , K 2 a , 2 bfor a , b ≥ 1 , K 2, 3 and K 3, 3 . In this paper, I prove that for all s , t ≥ 1 , if there exists a K s , t ‐design of order N , then there exists a K s , t ‐design of order n for all n ≡ N (mod 2 s t ) 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.