On the triangle clique cover and Kt clique cover problems

Hoang Dau, Olgica Milenkovic, Gregory J. Puleo

Research output: Contribution to journalArticlepeer-review

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

Original languageEnglish (US)
Article number111627
JournalDiscrete Mathematics
DOIs
StateAccepted/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

Fingerprint Dive into the research topics of 'On the triangle clique cover and K<sub>t</sub> clique cover problems'. Together they form a unique fingerprint.

Cite this