Complete Bipartite Free Graphs

M. Cera1, A. Dianez2, P. Garcia-Vazquez1, J.C. Valenzuela3
1E.U.LT. Agricola, Universidad de Sevilla, Spain.
2E.T.S. Arquitectura, Universidad de Sevilla, Spain.
3E.P.S. Algeciras, Universidad de Cédiz, Spain.

Abstract

The study of the maximum size \(ex(n; K_{t,t})\) of a graph of order \(n\) not containing the complete bipartite graph \(K_{t,t}\) as a subgraph is the aim of this paper. We show an upper bound for this extremal function that is optimum for infinitely many values of \(n\) and \(t\). Moreover, we characterize the corresponding family of extremal graphs.