Extremal and asymptotic properties of irreducible coverings of graphs by cliques

Abstract

A clique of a graph G is a complete subgraph of GG 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−1s−1 cliques from C is a proper subset of the vertex-set of GG. 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−2n−2 and n−3n−3 cliques and the structure of irreducible coverings for bipartite and nonbipartite cases. Some conjectures and open problems are proposed.