COMPLETE MULTIPARTITE DECOMPOSITIONS OF COMPLETE GRAPHS AND COMPLETE n-PARTITE GRAPHS

摘要

In this paper, a new concept of an optimal complete multipartite decomposition of type 1 (type 2) of a complete n-partite graph Q_n is proposed and another new concept of a normal complete multipartite decomposition of K_n is introduced. It is showed that an optimal complete multipartite decomposition of type 1 of K_n is a normal complete multipartite decomposition. As for any complete multipartite decomposition of K_n, there is a derived complete multipartite decomposition for Q_n. It is also showed that any optimal complete multipartite decomposition of type 1 of Q_n is a derived decomposition of an optimal complete multipartite decomposition of type 1 of K_n. Besides, some structural properties of an optimal complete multipartite decomposition of type 1 of K_n are given.