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.
@article{10_37236_11463,
author = {Pavel Shuldiner and R. Wayne Oldford},
title = {How many cliques can a clique cover cover?},
journal = {The electronic journal of combinatorics},
year = {2023},
volume = {30},
number = {2},
doi = {10.37236/11463},
zbl = {1519.05126},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11463/}
}
TY - JOUR
AU - Pavel Shuldiner
AU - R. Wayne Oldford
TI - How many cliques can a clique cover cover?
JO - The electronic journal of combinatorics
PY - 2023
VL - 30
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/11463/
DO - 10.37236/11463
ID - 10_37236_11463
ER -
%0 Journal Article
%A Pavel Shuldiner
%A R. Wayne Oldford
%T How many cliques can a clique cover cover?
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/11463/
%R 10.37236/11463
%F 10_37236_11463
Pavel Shuldiner; R. Wayne Oldford. How many cliques can a clique cover cover?. The electronic journal of combinatorics, Tome 30 (2023) no. 2. doi: 10.37236/11463
