Journal of Prime Research in Mathematics

Extremal and asymptotic properties of irreducible coverings of graphs by cliques

Ioan Tomescu
Faculty of Mathematics and Computer Sciences, University of Bucharest, Str. Academiei, 14, 010014 Bucharest, Romania.
\(^{1}\)Corresponding Author: ioan@fmi.unibuc.ro

Abstract

A clique of a graph G is a complete subgraph of \(G\) which is maximal relatively to set inclusion and a covering C of G consisting of s cliques is an irreducible covering if the union of any \(s − 1\) cliques from C is a proper subset of the vertex-set of \(G\). Some discrete optimization problems involve irreducible coverings of graphs: minimization of Boolean functions, minimization of incompletely specified finite automata, finding the chromatic number of a graph. This paper surveys some recent results by the author on the irreducible coverings of graphs by cliques: the recurrence relation and the exponential generating function of the number of irreducible coverings for bipartite graphs, asymptotic behavior of these numbers and of the maximum number of irreducible coverings by cliques of an n-vertex graph as n tends to infinity, extremal graphs of order n for irreducible coverings by \(n − 2\) and \(n − 3\) cliques and the structure of irreducible coverings for bipartite and nonbipartite cases. Some conjectures and open problems are proposed.