Back to Search Start Over

An extremal problem concerning graphs not containing Kt and Kt,t,t

Authors :
Ervin Győri
Yoomi Rho
Source :
Discrete Mathematics. 303:56-64
Publication Year :
2005
Publisher :
Elsevier BV, 2005.

Abstract

Brualdi and Mellendorf raised the following problem as a modification of Turan's theorem. Let t and n be positive integers with n>=t>=2. Determine the maximum number of edges of a graph of order n that contains neither K"t nor K"t","t as a subgraph. They solved it for n=2t (see R.A. Brualdi, S. Mellendorf, Two extremal problems in graph theory, The Electron. J. Combin. 1 (1994) #R2). We consider the following similar modification of Turan's theorem. Let t and n be positive integers with n>=t>=2. Determine the maximum number of edges of a graph of order n that contains neither K"t nor K"t","t","t as a subgraph. We solve it for n=3t.

Details

ISSN :
0012365X
Volume :
303
Database :
OpenAIRE
Journal :
Discrete Mathematics
Accession number :
edsair.doi...........fac9685ec598edc8fc4c15f13fb60b66
Full Text :
https://doi.org/10.1016/j.disc.2004.12.017