### 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 - Jan 1 2019 |

### Fingerprint

### 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

### Cite this

_{t}clique cover problems.

*Discrete Mathematics*, [111627]. https://doi.org/10.1016/j.disc.2019.111627

**On the triangle clique cover and K _{t} clique cover problems.** / Dau, Hoang; Milenkovic, Olgica; Puleo, Gregory J.

Research output: Contribution to journal › Article

_{t}clique cover problems. Discrete Mathematics. 2019 Jan 1. 111627. https://doi.org/10.1016/j.disc.2019.111627

}

TY - JOUR

T1 - On the triangle clique cover and Kt clique cover problems

AU - Dau, Hoang

AU - Milenkovic, Olgica

AU - Puleo, Gregory J.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - An edge clique cover of a graph is a set of cliques that covers all edges of the graph. We generalize this concept to Kt 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 Kt clique cover problem on a superclass of chordal graphs. We also prove that the Kt clique cover problem is NP-hard.

AB - An edge clique cover of a graph is a set of cliques that covers all edges of the graph. We generalize this concept to Kt 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 Kt clique cover problem on a superclass of chordal graphs. We also prove that the Kt clique cover problem is NP-hard.

KW - Community detection

KW - Edge clique cover

KW - Graph clustering

KW - Intersection number

KW - Triangle clique cover

KW - Turan graph

UR - http://www.scopus.com/inward/record.url?scp=85071693490&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85071693490&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2019.111627

DO - 10.1016/j.disc.2019.111627

M3 - Article

AN - SCOPUS:85071693490

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

M1 - 111627

ER -