3
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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). $\endgroup$ Dec 29 '20 at 11:17
4
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Nice, thank you! The two coverings have the same sum of clique sizes; do you think we may go further and find a minimalist covering with a sum of clique size strictly lower than the one of minimal coverings? $\endgroup$ Dec 29 '20 at 10:54
  • 2
    $\begingroup$ A friend just pointed me the following paper: Assignment-minimum clique coverings (Ennis, Fayle, Ennis, 2012) that seems to solve the question. $\endgroup$ Dec 29 '20 at 11:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.