On the Triangle Clique Cover and $K_t$ Clique Cover Problems

Abstract

An edge clique cover of a graph is a set of cliques that covers all edges of the graph. We generalize this concept to "$K_t$ clique cover", i.e. a set of cliques that covers all complete subgraphs on $t$ vertices of the graph, for every $t\ge 1$. In particular, we extend a classical result of Erdös, Goodman, and Pósa (1966) on the edge clique cover number ($t=2$), also known as the intersection number, to the case $t=3$. The upper bound is tight, with equality holding only for the Turán graph $T(n,3)$. We also extend an algorithm of Scheinerman and Trenk (1999) to solve a weighted version of the $K_t$ clique cover problem on a superclass of chordal graphs. We also prove that the $K_t$ clique cover problem is NP-hard.

14 pages, 1 figure. This version fixes some issues with the NP-hardness proof and some other minor errors

References in corpus (3)

• Uncovering the overlapping community structure of complex networks in nature and society
• Higher-order organization of complex networks
• Triadic closure as a basic generating mechanism of communities in complex networks

Cited by in corpus (1)

• Directed Intersection Representations and the Information Content of Digraphs