# Minimal clique edge cover vs minimalist (assignment-minimum) ones

Given a graph $$G=(V,E)$$, a clique edge cover is a collection $$C$$ of subsets of $$V$$ such that each element $$c$$ of $$C$$ is a clique ($$c \times c \subseteq E$$) and $$G$$ is the union of these cliques ($$E = \bigcup_{c\in C} c\times c$$).

The cover is said to be minimal if $$|C|$$ is minimal, i.e. the number of cliques used to cover the graph is minimal.

Let us say that the cover is minimalist if $$\sum_{c\in C} |c|$$, i.e. the sum of clique sizes, is minimal.

(Is there a better term than minimalist here? Does it appear in the literature?)

There exists minimal covers that are not minimalist covers.

Consider for instance, the graph where $$V=\{a,b,c,d,e\}$$ and $$E$$ is covered by $$C = \{\{a,b,c\}, \{b,c,d\}, \{c,d,e\}\}$$. This is a minimal covering of the graph, but not a minimalist one, since it is also covered by $$\{\{a,b,c\}, \{b,d\}, \{c,d,e\}\}$$.

Question: Is the converse true? Is there any graph having a minimalist cover that contains more than the minimal number of cliques needed to cover it?

• It turns out that minimalist covers are known as assignment-minimum coverings (which I will add to the question title), and that there are graphs for which no minimum clique covering is assignment-minimum, see "Assignment-minimum clique coverings" (Ennis, Fayle, Ennis, 2012). – Matthieu Latapy Dec 29 '20 at 11:17

Consider a graph on vertex set $$V_1\cup V_2\cup V_3\cup V_4\cup \{a,b,c,d\}$$ where $$|V_1|=|V_2|=|V_3|=|V_4|=n$$. The edge set $$E$$ is covered by $$C=\{V_1\cup\{a,c\},V_2\cup\{a,d\},V_3\cup\{b,c\},V_4\cup\{b,d\},\{a,b\},\{c,d\}\}$$.
When $$n$$ is large enough, any minimalist cover must contain the four maximum cliques $$V_1\cup\{a,c\}$$ and so on, so it is not hard to show that $$C$$ is minimalist. However replacing the two edges $$\{a,b\}$$ and $$\{c,d\}$$ with a single clique $$\{a,b,c,d\}$$ results in less number of cliques.