How many cliques can a clique cover cover?

Abstract

This work examines the problem of clique enumeration on a graph by exploiting its clique covers. The principle of inclusion/exclusion is applied to determine the number of cliques of size $r$ in the graph union of a set $\mathcal{C}=\{c_1,\dots ,c_m\}$ of $m$ cliques. This leads to a deeper examination of the sets involved and to an orbit partition, $\Gamma$, of the power set $\mathcal{P}({\mathcal{N}}_m)$ of ${\mathcal{N}}_m=\{1,\dots ,m\}$. Applied to the cliques, this partition gives insight into clique enumeration and yields new results on cliques within a clique cover, including expressions for the number of cliques of size $r$ as well as generating functions for the cliques on these graphs. The quotient graph modulo this partition provides a succinct representation to determine cliques and maximal cliques in the graph union. The partition also provides a natural and powerful framework for related problems, such as the enumeration of induced connected components, by drawing upon a connection to extremal set theory through intersecting sets.