2
$\begingroup$

Given a graph $G$ and the set $C_k(G)$ of the $k$-cliques in $G$, one can build a clique graph $H$ whose vertices $c_i\in C_k(G)$ are connected if the vertex sets of $c_i$ and $c_j$ have an intersection of cardinality $k-1$.

This construction is useful when one is interested in clique percolation.

My question is the following: when is $H\simeq G$ ?


An example:

$G$ formed by the 3-cliques $\{1,2,3\}$ and $\{4,5,6\}$, as well as the 4 clique $\{2,3,4,5\}$.

The set of 3 cliques is $c_1=\{1,2,3\}$, $c_2=\{2,3,4\}$, $c_3=\{2,3,5\}$, $c_4=\{3,4,5\}$, $c_5=\{2,4,5\}$ and $c_6=\{4,5,6\}$.

One can verify that $H$ has the following edge set: $\{(c_1,c_2), (c_1,c_3), (c_2,c_3), (c_2,c_4), (c_2,c_5), (c_3,c_4), (c_3,c_5), (c_4,c_5), (c_4,c_6),(c_5,c_6)\}$, i.e. it is isomorphic to $G$.

Is this graph special?

$\endgroup$
2
  • 4
    $\begingroup$ There is a related notion of "self-clique graphs" which has a sizable literature. $\endgroup$ Apr 18, 2016 at 5:16
  • $\begingroup$ Thank you for the pointer, it's exactly what I was looking for. $\endgroup$
    – jgyou
    Apr 18, 2016 at 5:33

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.