On Idomatic Partitions of Direct Products of Complete Graphs

摘要

Independent dominating sets in the direct product of four complete graphs are considered. Possible types of such sets are classified. The sets in which every pair of vertices agree in exactly one coordinate, called T_1-sets, are explicitly described. It is proved that the direct product of four complete graphs admits an idomatic partition into T_1-sets if and only if each factor has at least three vertices and the orders of at least two factors are divisible by 3.