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

Question

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?

Answer 1

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.