On Clique Coverings of Complete Multipartite Graphs

Abstract

A clique covering of a graph $G$ is a set of cliques of $G$ such that any edge of $G$ is contained in one of these cliques, and the weight of a clique covering is the sum of the sizes of the cliques in it. The sigma clique cover number $scc(G)$ of a graph $G$, is defined as the smallest possible weight of a clique covering of $G$. Let $K_t(d)$ denote the complete $t$-partite graph with each part of size $d$. We prove that for any fixed $d\ge 2$, we have $$\underset{t\to \infty }{\lim }scc(K_t(d))=\frac{d}{2}t\log t.$$ This disproves a conjecture of Davoodi, Javadi and Omoomi.