Decomposition of a Complete Multi-Partite Graph into Isomorphic Claws
Shinsei Tazawa · SIAM Journal on Algebraic and Discrete Methods · 1985
A graph is called a complete m-partite graph, denoted by $K_m ( n_1 ,n_2 , \cdots ,n_m )$, if its point set is partitioned into m subsets of $n_1 ,n_2 , \cdots ,n_m $ points each such that every pair of points in the same subset is not adjacent and if each point in one subset is adjacent to all points in the other subsets. A complete bipartite graph $K_2 ( 1,c )$ with $c + 1$ points and c lines is called a claw of degree c. $K_m ( n_1 ,n_2 , \cdots ,n_m )$ is said to have a claw-decomposition of degree c if it is a union of line-disjoint subgraphs each isomorphic to a claw of degree c. In this paper, a necessary and sufficient condition for $K_m ( n_1 ,n_2 , \cdots ,n_m )$ to have a claw-decomposition of degree c is given.