A new Turan-type theorem for cliques in graphs

被引：10

作者：

Eckhoff, J ^{[1
]}

机构：

[1] Univ Dortmund, Fachbereich Math, D-44221 Dortmund, Germany

来源：

DISCRETE MATHEMATICS | 2004年 / 282卷 / 1-3期

关键词：

Turan's theorem; Zykov's theorem; clique vectors;

D O I：

10.1016/j.disc.2003.11.007

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Turin's theorem (Mat. Fiz. Lapok 48 (1941) 436) (or rather its extension by Zykov (Mat. Sbomik 24 (66) (1949) 163) answers the following question: For k = 2,..., r, what is the maximum number of k-cliques (i.e., subgraphs on k vertices) in a finite graph G, given the clique number r and the number of vertices of G? Here we address-and answer -the following closely related question: For k = 3,...,r, what is the maximum number of k-cliques in G, given the clique number r and the number of edges of G? We also prove a "stability theorem" which shows that our result is best possible in a strong sense. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：113 / 122

页数：10

共 14 条

[1]

Andrasfai B., 1974, Discrete Mathematics, V8, P205, DOI 10.1016/0012-365X(74)90133-2

[2]

BILLERA LJ, 2003, HDB DISCRETE COMPUTA, P291

[3]

Bollobas B., 1978, EXTREMAL GRAPH THEOR

[4] On colouring the nodes of a network [J].

Brooks, RL .

PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1941, 37 :194-197

[5] The maximum number of triangles in a K4-free graph [J].

Eckhoff, J .

DISCRETE MATHEMATICS, 1999, 194 (1-3) :95-106

[6]

ECKHOFF J, UNPUB AM MATH MONTHL

[7]

Erdo P., 1962, Magyar Tud. Akad. Mat. Kutato Int. Kozl, VA3, P459

[8]

FISHER DC, 1990, C NUMER, V70, P217

[9] SHADOWS OF COLORED COMPLEXES [J].

FRANKL, P ;

FUREDI, Z ;

KALAI, G .

MATHEMATICA SCANDINAVICA, 1988, 63 (02) :169-178

[10]

Hadziivanov N. G., 1976, C R ACAD BULGARE SCI, V29, P1567

← 1 2 →