Graph whose smallest edge clique cover is not the collection of all maximal cliques

138 Views Asked by At

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}$?

1

There are 1 best solutions below

1
On BEST ANSWER

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