TAILIEUCHUNG - Báo cáo toán học: "Irreducible coverings by cliques and Sperner’s theorem"

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 .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.