An ordered Turan problem for bipartite graphs

作者：Timmons Craig^*

来源：Electronic Journal of Combinatorics, 2012, 19(4): P43.

• Turan problem
• bipartite graphs

Let F be a graph. A graph G is F-free if it does not contain F as a subgraph. The Turan number of F, written ex(n, F), is the maximum number of edges in an F-free graph with n vertices. The determination of Turan numbers of bipartite graphs is a challenging and widely investigated problem. In this paper we introduce an ordered version of the Turan problem for bipartite graphs. Let G be a graph with V(G) = {1, 2, ..., n} and view the vertices of G as being ordered in the natural way. A zig-zag K-s,K-t, denoted Z(s,t), is a complete bipartite graph K-s,K-t whose parts A = {n(1) < n(2) < ... < n(s)} and B = {m(1) < m(2) < ... < m(t)} satisfy the condition n(s) < m(1). A zig-zag C-2k is an even cycle C-2k whose vertices in one part precede all of those in the other part. Write Z(2k) for the family of zig-zag 2k-cycles. We investigate the Turan numbers ex(n, Z(s,t)) and ex(n, Z(2k)). In particular we show ex(n, Z(2,2)) <= 2/3 n(3/2) + O(n(5/4)). For infinitely many n we construct a Z(2,2)-free n-vertex graph with more than (n - root n - 1) + ex(n, K-2,K-2) edges.

• 出版日期2012-12-13