On the triangle clique cover and Kt clique cover problems

Hoang Dau, Olgica Milenkovic, Gregory J. Puleo

Research output: Contribution to journalArticle

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

Fingerprint

Clique
Triangle
Cover
Computational complexity
Intersection number
Graph in graph theory
Upper bound
Chordal Graphs
Subgraph
Equality
NP-complete problem
Generalise

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

On the triangle clique cover and Kt clique cover problems. / Dau, Hoang; Milenkovic, Olgica; Puleo, Gregory J.

In: Discrete Mathematics, 01.01.2019.

Research output: Contribution to journalArticle

@article{43a04538d33b4253b7d8844fc2aca75b,
title = "On the triangle clique cover and Kt 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 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{\"o}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{\'a}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.",
keywords = "Community detection, Edge clique cover, Graph clustering, Intersection number, Triangle clique cover, Turan graph",
author = "Hoang Dau and Olgica Milenkovic and Puleo, {Gregory J.}",
year = "2019",
month = "1",
day = "1",
doi = "10.1016/j.disc.2019.111627",
language = "English (US)",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",

}

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 -