2
$\begingroup$

Let $G=(V,E)$ be a simple, undirected graph. A clique decomposition is a set ${\cal C} \subseteq {\cal P}(V)$ such that

  1. $\emptyset \notin {\cal C}$,
  2. $C\in {\cal C}$ and $x\neq y \in C$ imply that $\{x,y\}\in E$ (that is every member of ${\cal C}$ is a clique),
  3. $\bigcup {\cal C} = V$, and
  4. $e=\{x,y\} \in E \implies$ there is $C\in{\cal C}$ such that $x,y\in C$.

Every graph has a clique decomposition (see the collection of all edges plus the isolated points). We call ${\cal C}$ minimal if $|{\cal C}|$ is minimal amongst all clique decompositions of $G$.

Question. If ${\cal C}, {\cal D}$ are minimal clique decompositions of a finite graph $G$, do we have ${\cal C}= {\cal D}$? (The same question could also be considered for infinite graphs, but I guess the answer is no for these.)

$\endgroup$
3
$\begingroup$

There can be multiple distinct decompositions of minimum size. Consider a triangular lattice tiling of a torus. The maximal cliques are triangles, so we certainly need $e(G) / 3$ cliques in any minimum-sized clique decomposition. But both the upwards pointing and downwards pointing triangles are a clique decomposition of this size.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Similar to Ben's answer is an octahedron which is $K_{2,2,2}$ and also $K_6$ minus a matching. There should be an enormous number of minimal covers for other complete multipartite graphs and for $K_{2m}$ with $m$ disjoint edges removed.

| cite | improve this answer | |
$\endgroup$

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.