On the maximum number of cliques in a graph

被引：51
作者：
Wood, David R. [1 ]
机构：
[1] Univ Politecn Cataluna, Dept Matemat Aplicada 2, Barcelona, Spain
来源：
GRAPHS AND COMBINATORICS | 2007年 / 23卷 / 03期
关键词：
extremal graph theory; Turan's Theorem; clique; complete subgraph; degeneracy; graph minor; planar graph; K-5-minor; K-3; K-3-minor;
D O I：
10.1007/s00373-007-0738-8
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Delta; (3) d-degenerate graphs with n vertices and m edges; (4) planar graphs with n vertices and m edges; and (5) graphs with n vertices and no K-5-minor or no K-3,K-3-minor. For example, the maximum number of cliques in a planar graph with n vertices is 8(n - 2).
引用
收藏
页码：337 / 352
页数：16
相关论文
共 51 条
[1]  
[Anonymous], 1984, LAW HIST REV
[2]   A partial k-arboretum of graphs with bounded treewidth [J].
Bodlaender, HL .
THEORETICAL COMPUTER SCIENCE, 1998, 209 (1-2) :1-45
[3]   COMPLETE SUBGRAPHS OF R-CHROMATIC GRAPHS [J].
BOLLOBAS, B ;
ERDOS, P ;
SZEMEREDI, E .
DISCRETE MATHEMATICS, 1975, 13 (02) :97-107
[4]  
BOLLOBAS B, 1976, MATH PROC CAMBRIDGE, V80, P419, DOI 10.1017/S0305004100053056
[5]  
BOLLOBAS B, 1995, HDB COMBINATORICS, V2, P1231
[6]   The maximum number of triangles in a K4-free graph [J].
Eckhoff, J .
DISCRETE MATHEMATICS, 1999, 194 (1-3) :95-106
[7]   A new Turan-type theorem for cliques in graphs [J].
Eckhoff, J .
DISCRETE MATHEMATICS, 2004, 282 (1-3) :113-122
[8]   CONNECTIVITY, GRAPH MINORS, AND SUBGRAPH MULTIPLICITY [J].
EPPSTEIN, D .
JOURNAL OF GRAPH THEORY, 1993, 17 (03) :409-416
[9]   ON CLIQUES IN GRAPHS [J].
ERDOS, P .
ISRAEL JOURNAL OF MATHEMATICS, 1966, 4 (04) :233-&
[10]  
Erdos P., 1969, Casopis. pro pestovani. matematiky, V94, P290
123456