2
$\begingroup$

Let $G$ be an undirected simple graph. An edge clique cover of $G$ is a collection $\mathcal{C}$ of cliques (i.e., complete subgraphs) that cover all the edges of $G$. In other words, every edge belongs to at least one clique $C \in \mathcal{C}$. The smallest such collection of cliques $\mathcal{C}$ is sometimes known as the intersection number of $G$.

Clearly, we can take $\mathcal{C}$ to be the collection of all maximal cliques of $G$. This can also be optimal, i.e., there is no smaller $\mathcal{C}$ which is also an edge clique cover.

But is there an example of a graph such that its smallest edge clique cover is different from the collection of all maximal cliques? As a bonus question, do we know exactly when the collection of all maximal cliques is an optimal collection in terms of the number of elements in $\mathcal{C}$?

$\endgroup$
  • $\begingroup$ The bonus question part still remains, but I suspect this might be much more difficult. $\endgroup$ – advanced_learner Dec 14 '18 at 13:30
2
$\begingroup$

Consider the octahedron. All $8$ triangular faces are maximal cliques, however only $4$ of them is enough for an edge clique cover.

$\endgroup$
  • $\begingroup$ Yes, perfect. That is indeed a valid counterexample, thank you! $\endgroup$ – advanced_learner Dec 14 '18 at 13:28

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.