























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, $Γ$, 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。