Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)
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.
This page was built for publication: How many cliques can a clique cover cover?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6115508)
