## 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≥1. In particular, we extend a classical result of Erdös et al. (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). As part of the proof, we obtain new upper bounds on the classical intersection number, which may be of independent interest. 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.

Original language | English (US) |
---|---|

Article number | 111627 |

Journal | Discrete Mathematics |

DOIs | |

State | Accepted/In press - 2019 |

## Keywords

- Community detection
- Edge clique cover
- Graph clustering
- Intersection number
- Triangle clique cover
- Turan graph

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics