Turán type problems forbidding complete graphs and complete multipartite graphs together

Yoomi Rho (노유미)

Dept. of Mathematics, Univ. of Incheon, Incheon, Korea.

Dept. of Mathematics, Univ. of Incheon, Incheon, Korea.

2008/11/28 Fri, 4PM-5PM

A Turán type problem looks for the maximum number of edges of a graph of a given order that does not contain given forms of graphs as subgraphs. These given forms of subgraphs are called the

*forbidden graphs*of the problem. This problem also looks for the forms of graphs which have the maximum number of edges. This line of research is started by Turán who solved the problem forbidding complete graphs in 1941. Problems forbidding complete bipartite graphs or even cycles have been considered. Also there are asymptotic results on problems forbidding complete multipartite graphs. In 1994, Brualdi and Mellendorf raised the following problem which forbids a complete graph and a complete bipartite graph together.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 also solved this problem when n=2t. Obviously when n<2t, the problem reduces to Turán's problem which forbids only K_{t}. We solve the problem when n=2t+1. We raise a problem which forbids K_{t} and K_{t,n-t} together and a problem which forbids K_{t} and K_{t,t,t} together.

Tags: 노유미