THE MAXIMAL NUMBER OF INDUCED R-PARTITE SUBGRAPHS

被引：13

作者：

BOLLOBAS, B

EGAWA, Y

HARRIS, A

JIN, GP

机构：

[1] UNIV CAMBRIDGE,DEPT PURE MATH & MATH STAT,CAMBRIDGE,ENGLAND

[2] SCI UNIV TOKYO,DEPT APPL MATH,TOKYO 162,JAPAN

[3] LONDON SCH ECON,DEPT OPERAT RES,LONDON,ENGLAND

来源：

GRAPHS AND COMBINATORICS | 1995年 / 11卷 / 01期

关键词：

D O I：

10.1007/BF01787417

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper, we extend earlier results concerning the maximal number of induced complete r-partite graphs in a graph G of order n. In particular, we show that if t > 1 + log r, then the maximal number of induced K-r(t)'s is achieved in the case of the Turan graph T-r(n), and that this bound on t is essentially best possible.

引用

页码：1 / 19

页数：19

共 9 条

[1]

Beineke L.W., Harary F., The maximum number of strongly connected subtournaments, Canadian Mathematical Bulletin, 8, pp. 491-498, (1965)

[2]

Bollobas B., Extremal Graph Theory, pp. xx-488, (1978)

[3]

Bollobas B., Nara C., Tachibana S., The maximal number of induced complete bipartite subgroups, Discrete Math., 62, pp. 271-275, (1986)

[4]

Brown J., Sidorenko A., The inducibility of complete bipartite graphs, Journal of Graph Theory, 18, pp. 629-645, (1994)

[5]

Erdos P., On the number of complete subgraphs contained in certain graphs, Publ. Math. Inst. Hungar. Acad. Sci., 1, pp. 459-464, (1962)

[6]

Exoo G., Dense packing of induced subgraphs, Ars Combinatoria, 22, pp. 5-10, (1986)

[7]

Gyori E., Pach J., Simonovits M., On the maximal number of certain subgraphs in K<sub>r</sub>-free graphs, Graphs and Combinatorics, 7, pp. 31-37, (1991)

[8]

Moon J.W., Moser L., On cliques in graphs, Israel J. Math., 3, pp. 23-28, (1965)

[9]

Pippenger N., Golumbic M., The inducibility of graphs, J. Comb. Theory, Ser. B, 19, pp. 189-203, (1975)

← 1 →