2022/06/29 by Pavel Shuldiner, Shuldiner, Pavel, R. Wayne Oldford +1
Mathematics · #Combinatorics (math.CO) #Commutative Algebra and Its Applications #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2206.14895
openalex publication_date 2022/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 C = \c1, …, cm\ of m cliques. This leads to a deeper examination of the sets involved and to an orbit partition, Γ, of the power set P(Nm) of Nm = \1, …, 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.