Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Irreducible coverings by cliques and Sperner’s theorem. | Irreducible coverings by cliques and Sperner s theorem Ioan Tomescu Faculty of Mathematics and Computer Science University of Bucharest Str. Academiei 14 R-70109 Bucharest Romania. ioan@ Submitted September 29 2002 Accepted October 22 2002. MR Subject Classifications 05C69 05C35 06A07 Abstract In this note it is proved that if a graph G of order n has an irreducible covering of its vertex set by n k cliques then its clique number w G k 1 if k 2 or 3 and w G py2j if k 4. These bounds are sharp if n k 1 for k 2 or 3 and n k ụk 2j for k 4 . Key Words clique irreducible covering antichain Sperner s theorem 1 Definitions and preliminary results For a graph G having vertex set V G and edge set E G a clique is a subset of vertices inducing a complete subgraph of G which is maximal relative to set inclusion. The clique number of G denoted G is the size of a largest clique in G 1 . A k-clique is a clique containing k vertices. A family of different cliques c1 c2 . cs of G is a covering of G by cliques if us i ci V G . A covering C of G consisting of s cliques c1 . cs of G will be called an irreducible covering of G if the union of any s 1 cliques from C is a proper subset of V G . This means that there exist s vertices x1 . xs 2 V G that are uniquely covered by cliques of C . xi 2 Ufc i ck for every 1 i s. k i If G Kp q every clique of G is an edge and an irreducible covering by edges of Kp q consists of a set of vertex-disjoint stars some centered in the part with p vertices and others in the part with q vertices of Kpq which cover together all vertices of Kpq. Some properties of the numbers N p q of all irreducible coverings by edges of Kp q were deduced in 8 and the exponential generating function of these numbers was given in 9 . Also by denoting I n n k the maximum number of irreducible coverings of the vertices of an n-vertex graph by n k cliques in 8 it was shown that limn x I n n k 1 n a k where a k is the greatest number of cliques a graph .
