How many cliques can a clique cover cover? (Q6115508)

Summary: 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, \ldots, 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, \ldots, 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.