Topological minors in bipartite graphs

Topological minors in bipartite graphs Camino BALBUENA Departament de Matem`atica Aplicada III, UPC, Barcelona, Spain E-mail: [email protected] Mart´ın CERA, P. GARCIA-VAZQUEZ Departamento de Matem´atica Aplicada I, Universidad de Sevilla, Sevilla, Spain E-mail: mcer[email protected], p[email protected] Juan Carlos VALENZUELA Departamento de Matem´aticas, Universidad de C´adiz, Algeciras, Spain E-mail: [email protected] Abstract For a bipartite graph Gon mand nvertices, respectively, in its vertices classes, and for integers sand tsuch that 2 ≤s≤t, 0≤m−s≤n−t, and m+n≤2s+t−1, we prove that if Ghas at least mn −(2(m−s) + n−t) edges then it contains a subdivision of the complete bipartite K(s,t)with svertices in the m-class and tvertices in the n-class. Furthermore, we characterize the corresponding extremal bipartite graphs with mn−(2(m−s)+n−t+1) edges for this topological Turan type problem. Key words. bipartite graphs, extremal graph theory, topological minor MR(2000) Subject Classification 05C35, 05C40 1 Introduction Throughout this paper, only undirected simple graphs without loops or multiple edges are considered. Unless otherwise stated, we follow the book by Diestel (cf. [18]) for terminology and definitions. 1 Two well-known extensions of the Tur´an problem (cf. [1]) are the Tur´an topological problem and the Zarankiewicz problem. The former one consists of estimating the extremal function ex(n, T Kp) which represents the maximum number of edges of a graph on nvertices free of a topological minor T Kpof a complete graph on pvertices (see Bollob´as’ excellent monograph (cf. [4]) devoted to this subject and the contributions on this topic (cf. [5, 9, 14, 19, 20, 22])). The second was stated by Zarankiewicz (cf. [2]) who studied the maximum size of a bipartite graph on (m, n) vertices, denoted by z(m, n;s, t) that contains no bipartite complete K(s,t)subgraph with svertices in the m-class and tvertices in the n-class. For a survey of this problem we also refer the reader to Section VI.2 of the book by Bollob´as (cf. [4]). Most of the contributions are bounds for the function z(m, n;s, t) when s, t are fixed and m, n are much larger than s, t (cf. [6, 7, 12]). Other contributions provide exact values of the extremal function (cf. [10, 13, 23]). Recent results on some problems involving the existence of a complete bipartite graph or a subdivision of a complete bipartite graph as a subgraph can be found in the literature (cf. [15, 16, 17, 21, 24, 26, 27]). B¨ohme et al. (cf. [16]) studied the size of a k-connected graph free of either an induced path of a given length or a subdivision of a complete bipartite graph. K¨uhn and Osthus (cf. [17]) proved that for any graph Hand for every integer sthere exists a function f=f(H, s) such that every graph of size at least fcontains either a Ks,s as a subgraph or an induced subdivision of H. Meyer (cf. [15]) also relates the size of a graph with the property of containing a minor of Ks,t. Other problems involving the existence of maximum matching in graphs are considered (cf. [26]). And involving the existence of 2-factors in bipartite graphs and k-factors in regular graphs can be found (cf. [21, 24, 28]). Combining the topological version of the Tur´an problem for complete graphs with the Zarankiewicz problem, we introduce the extremal function tz(m, n;s, t) as a natural extension. The function tz(m, n;s, t) is defined as the maximum size of a (m, n)-bipartite graph free of a topological minor T K(s,t)of a complete bipartite K(s,t)with svertices in the m-class and tvertices in the n-class. In 1998 Bollob´as and Thomason (cf. [8]) proved that the function ex(n;T Kp) is upper bounded by cp2n. From this contribution together with the fact that the example, due to Jung (cf. [3]) and improved by Luczak (cf. [11]), giving a lower bound is a bipartite graph, it follows that the extremal function tz(m, m;t, t) is asymptotically upper bounded by ct2n. The objective of this paper is to obtain exact values for this extremal function tz(m, n;s, t) and to characterize the corresponding extremal bipartite graphs for infinitely many related values of m, n, s, t. Namely, we determine the exact value of tz(m, n;s, t) and we characterize the family T Z(m, n;s, t) of extremal graphs for any values of m, n, s, t 2 satisfying 2 ≤m−s≤n−tand m+n≤2s+t−1. 1.1 Terminology and notations A subdivision of a graph His a graph T H obtained from Hby replacing the edges of Hwith internally disjoint paths. The branch vertices of T H are all those vertices that correspond to vertices of H. The complete bipartite graph K(s,t)is said to be a topological minor of a bipartite graph Gif T K(s,t)⊆G. Given two positive integers, m,n, a bipartite graph Gwith vertex classes Xand Yof cardinalities |X|=mand |Y|=n, is denoted by G= (X, Y ). The sets of vertices and edges of Gare denoted by V(G) = X∪Yand E(G), respectively, whereas v(G) and e(G) stand for the corresponding cardinalities. For a bipartite graph H= (X, Y ), the degree of a vertex vin the graph His denoted by dH(v) whereas ∆X(H) (resp. ∆Y(H)) stand for the maximum degree among vertices in the first class (resp. second class). Thus, ∆(H) = max{∆X(H),∆Y(H)}is the maximum degree of H. Let us consider two subsets of vertices {x1, x2, . . . , xp} ⊆ Xand {y1, y2, . . . , yp} ⊆ Y. Let us denote by H0,0=H, H1,0=H−{x1},H1,1=H1,0−{y1}, and for all i= 2, . . . , p, let us denoted by Hi,i−1=Hi−1,i−1−{xi} and Hi,i =Hi,i−1−{yi}. Next we introduce the notion of decreasing sequence of vertices in a bipartite graph H= (X, Y ). Definition 1.1 Given an integer p≥1and a bipartite graph H= (X, Y ), a subset of vertices of H, {x1, y1, x2, y2, . . . , xp, yp}, with {x1, . . . , xp} ⊆ Xand {y1, . . . , yp} ⊆ Y, is called a decreasing sequence of Hif the following assertions hold: (i) dHi−1,i−1(xi) = ∆X(Hi−1,i−1), for i= 1, . . . , p. (ii) dHi,i−1(yi)=∆Y(Hi,i−1), for i= 1, . . . , p. (iii) For each i= 1, . . . , p, either xiyi6∈ E(H)or every vertex y∈V(Hi,i−1)∩Ywith degree dHi,i−1(y) = ∆Y(Hi,i−1)is adjacent to vertex xiin H. Note that dH0,0(x1)≥dH1,1(x2)≥...≥dHp−1,p−1(xp)≥∆X(Hp,p) and dH1,0(y1)≥dH2,1(y2)≥. . . ≥dHp,p−1(yp)≥∆Y(Hp,p), 3 and furthermore, e(H) = p X i=1 ¡dHi−1,i−1(xi) + dHi,i−1(yi)¢+e(Hp,p). 2 Exact values Let Gbe a bipartite graph G= (X, Y ) on mand nvertices in Xand Yrespectively. We will henceforth use Hto denote the bipartite complement of G, i.e., the bipartite graph H= (X, Y ) = K(m,n)−E(G). The problem of finding a T K(s,t)in a bipartite graph Gcan be formulated in terms of its bipartite complement H. Indeed, if G= (X, Y ) contains a T K(s,t)with set of branch vertices S∪T,S⊂X, T⊂Y, then the edges of the graph H[S∪T] are missing in Gand thus they must be replaced in Gwith internally disjoint paths passing through vertices of X\Sand vertices of Y\T. Since each of these paths must have odd length at least 3, it follows that e(H[S∪T]) ≤min{|X\S|,|Y\T|}. Hence, the following necessary but not sufficient condition on the induced subgraph H[S∪T] in order to determine whether K(s,t)is a topological minor of Gis immediate. Remark 2.1 Let G= (X, Y )be with |X|=mand |Y|=nand let Hbe the bipartite complement of G. If Gcontains a T K(s,t), then there exist S⊆Xand T⊆Ywith |S|=s,|T|=t, such that the number of edges of the subgraph induced by S∪Tin the bipartite complement of Gsatisfies e(H[S∪T]) ≤min{m−s, n −t}. Next, we obtain a lower bound on the maximum size of a (m, n)-bipartite graph free of a topological minor T K(s,t)of K(s,t). Proposition 2.1 Let m, n, s, t be integers such that 2≤s≤t, 0≤m−s≤n−t, and m+n≤2s+t−1. Then the bipartite graph G=K(m,n)−M, where Mis any matching of cardinality 2(m−s)+n−t+1, does not contain T K(s,t)and therefore, tz(m, n;s, t)≥mn −(2(m−s) + n−t+ 1) . Proof First, let us see that K(m,n)has a matching of cardinality 2(m−s) + n−t+ 1. This is clear because from 2 ≤s≤tand 0 ≤m−s≤n−t, it follows that m≤n, and from the hypothesis 4 m+n≤2s+t−1 it follows that 2(m−s) + n−t+ 1 = (m+n) + m−2s−t+ 1 ≤m≤n. Therefore, we may consider the bipartite graph G= (X, Y ) = K(m,n)−Mwhere Mis a matching of cardinality 2(m−s) + n−t+ 1 in K(m,n). Next let us see that K(s,t)is not a topological minor of G. For that, from Remark 2.1 it is enough to prove that e(H[S∪T]) > m −sfor any subsets S⊆Xand T⊆Y of cardinalities sand t, respectively, with s≤t. Observe that the number of isolated vertices in the class Yof His exactly n−(2(m−s) + n−t+ 1). It follows that the number of edges of H[X∪T] is e(H[X∪T]) ≥t−(n−(2(m−s) + n−t+ 1)) = 2m−2s+ 1. But since e(H[(X\S)∪T]) ≤m−s, then we have e(H[S∪T]) = e(H[X∪T]) −e(H[(X\S)∪T]) ≥2m−2s+ 1 −(m−s) =m−s+ 1 > m −s. Thus the result holds. Lemma 2.1 Let p≥1be an integer and let G= (X, Y )be a bipartite graph, with |X| ≥ pand |Y| ≥ p, and denote by H= (X, Y )the bipartite complement of G. Let {x1, y1, x2, y2, . . . , xp, yp}be any decreasing sequence of Hand denote by r=e(Hp,p). If r≥1and e(H)≤3p, then: (i) r≤p. (ii) ∆(Hp,p) = 1. (iii) {xp−(r−1)yp−(r−1), . . . , xpyp} ∩ E(H) = ∅. (iv) {ayp−(r−1), . . . , ayp} ∩ E(H) = ∅, for each a∈X\ {x1, . . . , xp}of degree dHp,p (a) = 1. (v) If r≥2, then {xp−(r−2)b, . . . , xpb}∩E(H) = ∅, for each b∈Y\{y1, . . . , yp}of degree dHp,p (b) = 1. Proof Since e(Hp,p) = r≥1 we deduce ∆X(Hp,p)≥1, ∆Y(Hp,p)≥1, following that dHi−1,i−1(xi)≥ 1 and dHi,i−1(yi)≥1 for i= 1, . . . , p, and therefore e(Hp,p) = e(H)− p X i=1 ¡dHi−1,i−1(xi) + dHi,i−1(yi)¢≤3p−2p=p, thus item (i) is proved. 5 If ∆X(Hp,p)≥2, then dHi−1,i−1(xi)≥2 for each i= 1, . . . , p, hence, e(H) = p X i=1 ¡dHi−1,i−1(xi) + dHi,i−1(yi)¢+e(Hp,p)≥3p+r > 3p, which is a contradiction. Analogously, we arrive at a contradiction if ∆Y(Hp,p)≥2. Thus, ∆X(Hp,p) = ∆Y(Hp,p) = 1, which implies ∆(Hp,p) = 1, hence item (ii) is shown. (iii) Let us denote the edges of Hp,p by e1=a1b1, . . . , er=arbr,ai∈X\ {x1, . . . , xp}and bi∈ Y\ {y1, . . . , yp}, for i= 1, . . . , r. By item (i) we know that r≤p. We reason by way of contradiction supposing that there exists j∈ {0, . . . , r −1}such that xp−jyp−j∈E(H). First we claim that dHp−j,p−j−1(yp−j) = 1. Otherwise, if dHp−j,p−j−1(yp−j)≥2 then dHi,i−1(yi)≥2, for i= 1, . . . , p −j and therefore, by (ii) we have e(H) = p−j X i=1 ¡dHi−1,i−1(xi) + dHi,i−1(yi)¢+ p X i=p−j+1 ¡dHi−1,i−1(xi) + dHi,i−1(yi)¢+e(Hp,p) ≥3(p−j) + 2j+r = 3p+ (r−j) >3p, the last inequality due to the fact that j≤r−1. Since this is a contradiction with the hypothesis, then ∆Y(Hp−j,p−j−1) = dHp−j,p−j−1(yp−j) = 1, yielding to dHi,i−1(yi) = 1, for i=p−j, . . . , p and dHp,p (bi) = 1, for i= 1, . . . , r. As {x1, y1, x2, y2, . . . , xp, yp}is a decreasing sequence of H, it follows that xp−jis adjacent in Hto each one of the vertices of the set {yp−j, . . . , yp, b1, . . . , br} because of point (iii) of Definition 1.1. That is, dHp−j−1,p−j−1(xp−j)≥j+1+r, which means that dHi−1,i−1(xi)≥j+ 1 + r≥2, for i= 1, . . . , p −jand therefore, e(H) = p−j X i=1 ¡dHi−1,i−1(xi) + dHi,i−1(yi)¢+ p X i=p−j+1 ¡dHi−1,i−1(xi) + dHi,i−1(yi)¢+e(Hp,p) ≥3(p−j) + 2j+r= 3p+ (r−j)>3p, again a contradiction. Thus xp−jyp−j6∈ E(H) for all j∈ {0, . . . , r −1}, hence item (iii) is valid. (iv) Note that r≥1 implies dHi−1,i−1(xi)≥1 and dHi,i−1(yi)≥1 for i= 1, . . . , p. We reason by way of contradiction supposing that there exists j∈ {0, . . . , r −1}such that ayp−j∈E(H) for a vertex a∈X\ {x1, . . . , xp}of degree dHp,p (a) = 1. Then dHp−j−1,p−j−1(a)≥2 and hence, dHi−1,i−1(xi)≥2, 6 for i= 1, . . . , p −j. Thus, e(H) = p−j X i=1 ¡dHi−1,i−1(xi) + dHi,i−1(yi)¢+ p X i=p−(j−1) ¡dHi−1,i−1(xi) + dHi,i−1(yi)¢+e(Hp,p) ≥3(p−j)+2j+r= 3p+ (r−j)>3p, because j≤r−1, against the hypothesis. (v) Since r≥2 then dHi−1,i−1(xi)≥1 and dHi,i−1(yi)≥1 for i= 1, . . . , p. We reason by way of contradiction supposing that there exists j∈ {0, . . . , r −2}such that xp−jb∈E(H) for a vertex b∈Y\ {y1, . . . , yp}of degree dHp,p (b) = 1. Then dHp−j−1,p−j−2(b)≥2 and hence, dHi,i−1(yi)≥2, for i= 1, . . . , p −j−1. Thus, e(H) = p−j−1 X i=1 ¡dHi−1,i−1(xi) + dHi,i−1(yi)¢+ p X i=p−j¡dHi−1,i−1(xi) + dHi,i−1(yi)¢+e(Hp,p) ≥3(p−j−1) + 2(j+ 1) + r= 3p+ (r−j−1) >3p, because j≤r−2, again a contradiction. Lemma 2.2 Let p≥2be an integer. Let G= (X, Y )be a bipartite graph with |X| ≥ pand |Y| ≥ p, and denote by H= (X, Y )the bipartite complement of G. Suppose that there exists a decreasing sequence of vertices U={x1, y1, x2, y2, . . . , xp, yp}of Hsuch that E(Hp,p) = {ab}with a∈Xand b∈Y. If e(H)≤3pthen there exists an (a, b)-path in Gwith its internal vertices belonging to U. Proof Since E(Hp,p) = {ab}, then ∆X(Hp,p)=∆Y(Hp,p) = 1, which implies that dHi−1,i−1(xi)≥1 and dHi,i−1(yi)≥1 for i= 1, . . . , p. If Gcontains the path a, yp, xp, b, then we are done. So assume that some of the edges ayp,xpyp,xpbis an edge of H. We know by Lemma 2.1 (iii) that xpyp6∈ E(H). If ayp∈E(H), then dHp−1,p−1(a)≥2, because {ayp, ab} ⊂ E(Hp−1,p−1). Then dHi−1,i−1(xi)≥2 and we get e(H) = p X i=1 ¡dHi−1,i−1(xi) + dHi,i−1(yi)¢+e(Hp,p)≥3p+ 1, which is a contradiction. Therefore we can suppose that xpb∈E(H) and ayp6∈ E(H). Then {xpb, ab} ⊂ E(Hp−1,p−2), following that dHp−1,p−2(b)≥2, which implies that dHi,i−1(yi)≥2, for i= 1, . . . , p −1. Since dHp,p−1(yp)≥1 and dHi−1,i−1(xi)≥1 for i= 1, . . . , p, it follows that e(H) = p−1 X i=1 ¡dHi−1,i−1(xi) + dHi,i−1(yi)¢+¡dHp−1,p−1(xp) + dHp,p−1(yp)¢+e(Hp,p) ≥3(p−1) + 2 + 1 = 3p. 7 This means that all the above inequalities become equalities, that is,      dHi,i−1(yi) = 2,for i= 1, . . . , p −1,and dHp,p−1(yp) = 1; dHi−1,i−1(xi) = 1,for i= 1, . . . , p. (1) Therefore we obtain that: •xpyp−16∈ E(H), because otherwise, {xpb, xpyp−1} ⊂ E(Hp−2,p−2) and thus, dHp−2,p−2(xp−1) = ∆X(Hp−1,p−1)≥2, contradicting (1). •xp−1b6∈ E(H), for if not, {xp−1b, xpb, ab} ⊂ E(Hp−2,p−3) and hence, dHp−2,p−3(yp−2) = ∆Y(Hp−2,p−3)≥3, against (1). •xp−1yp−16∈ E(H), because otherwise, dHp−2,p−3(yp−1)≥3 and therefore, dHp−2,p−3(yp−2)≥3, contradicting (1). Thus, it follows that {ayp, xpyp, xpyp−1, xp−1yp−1, xp−1b} ∩ E(H) = ∅. Consequently, there exists in Gthe path a, yp, xp, yp−1, xp−1, b, hence the result holds. Lemma 2.3 Let m, n, p be integers such that p≥2,m > p and n > p. Let G= (X, Y )be a bipartite graph with |X|=mand |Y|=n, and denote by H= (X, Y )the bipartite complement of G. If e(H)≤3p, then K(m−p,n−p)is a topological minor of G. Proof Let U={x1, y1, x2, y2, . . . , xp, yp}be a decreasing sequence of H. The graph Hp,p is a bipartite graph with vertex classes X∗=X\ {x1, . . . , xp}and Y∗=Y\ {y1, . . . , yp}, so |X∗|=m−pand |Y∗|=n−p. If e(Hp,p) = 0 then the bipartite complement of Hp,p is K(m−p,n−p)and the result follows. We may henceforth assume that e(Hp,p)>0, or in other words ∆X(Hp,p)≥1 and ∆Y(Hp,p)≥1, thus dHi−1,i−1(xi)≥1 and dHi,i−1(yi)≥1 for i= 1, . . . , p. Then by Lemma 2.1 we have e(Hp,p) = r≤p and ∆(Hp,p) = 1. Let us denote the edges of Hp,p by e1=a1b1, . . . , er=arbr,ai∈X∗and bi∈Y∗, for i= 1, . . . , r. In order to prove that Gcontains T K(m−p,n−p)with set of branch vertices X∗∪Y∗, we will show the existence of vertex disjoint (ai, bi)-paths in G,i= 1, . . . , r, with internal vertices from U. As e(H)≤3p, if r= 1 then the bipartite complement of Hp,p is Km−p,n−p−e1. Thus, by Lemma 2.2, the bipartite graph Gcontains T Km−p,n−pand we are done. Hence assume that 2≤r≤p, then by Lemma 2.1 (iii), (iv), (v), for each i= 1, . . . , r and j= 0, . . . , r −2, there exists in Gthe path ai, yp−j, xp−j, bi. Thus, we only must show that there exists i∈ {1, . . . , r}such that 8 the path ai, yp−(r−1), xp−(r−1), biis contained in G. Otherwise, since xp−(r−1)yp−(r−1) ∈E(G) and aiyp−(r−1) ∈E(G) for all i= 1, . . . , r, because of Lemma 2.1, we deduce that xp−(r−1)bi∈E(H) for all i= 1, . . . , r, that is, dHp−r,p−r(xp−(r−1))≥rand therefore, dHi−1,i−1(xi)≥rfor i= 1, . . . , p −(r−1). Then since 2 ≤r≤pit follows that e(H) = p−(r−1) X i=1 ¡dHi−1,i−1(xi) + dHi,i−1(yi)¢+ p X i=p−(r−2) ¡dHi−1,i−1(ik) + dHi,i−1(yi)¢+e(Hp,p) ≥(r+ 1)(p−(r−1)) + 2(r−1) + r = 3p+ 1 + (r−2)(p−r+ 1) >3p which is a contradiction. Hence there exists i∈ {1, . . . , r}such that the path ai, yp−(r−1), xp−(r−1), bi is contained in G. Without loss of generality we may assume that i=r. Then there exist in Gthe vertex-disjoint paths aj, yp−(j−1), xp−(j−1), bjfor j= 1, . . . , r. Thus, Gcontains T K(m−p,n−p)and this finishes the proof. The following lemma gives a sufficient condition on the size of a bipartite graph in order to contain a complete bipartite graph as a topological minor. Lemma 2.4 Let m, n, s, t be integers such that 2≤m−s≤n−t. Let G= (X, Y )be a bipartite graph with |X|=m,|Y|=n. If the bipartite complement Hof Ghas size e(H)≤2(m−s) + n−t, then K(s,t)is a topological minor of G. Proof Set p=m−sand q=n−t, then 2 ≤p≤qand e(H)≤2p+q. First, suppose that p=q. Thus the bipartite graph Hhas size at most 3p, and by Lemma 2.3, we obtain that K(m−p,n−p)=K(s,t) is a topological minor of G. Hence, assume that p < q. Without loss of generality, we may assume that the vertices of the partite set Yare ordered in such a way that dH(y1)≥dH(y2)≥ · · · ≥ dH(yn). Set Y0={y1, . . . , yq−p} ⊆ Yand let us consider the bipartite graph H0= (X, Y \Y0). Observe that |X|=mand |Y\Y0|=n−(q−p) = t+p. If e(H0) = 0 then the bipartite complement G0of H0 is the complete bipartite graph K(m,t+p). Since G0is a subgraph of Gand K(s,t)⊆K(m,t+p), then G contains a K(s,t)and we are done. So, we may assume that e(H0)>0, which implies that dH(yi)≥1 for i= 1, . . . , q −p. Hence, e(H0) = e(H)−Pq−p i=1 dH(yi)≤2p+q−(q−p)≤3p, and therefore, from Lemma 2.3, it follows that K(m−p,t+p−p)=K(s,t)is a topological minor of G. 9 dHj,j−1(yj)≥rfor j= 1, . . . , p −(r−1), and dHj−1,j−1(xj)≥2 for j= 1, . . . , p −(r−1). Thus, e(H) = p−(r−1) X j=1 ¡dHj−1,j−1(xj) + dHj,j−1(yj)¢+ p X j=p−(r−2) ¡dHj−1,j−1(xj) + dHj,j−1(yj)¢+e(Hp,p) ≥(r+ 2)(p−(r−1)) + 2(r−1) + r = 3p+1+(r−2)(p−r) + p−1 >3p+ 1, since 2 ≤r < p and p > 1, which is a contradiction. Case 3. Assume that there exist i0, j0∈ {1, . . . , r}such that xp−(r−1)bi06∈ E(H) and aj0yp−(r−1) 6∈ E(H). Clearly i06=j0, because xp−(r−1)yp−(r−1) 6∈ E(H) (by Lemma 3.1) and by hypothesis, the path ai, yp−(r−1), xp−(r−1), bidoes not exist in Gfor all i= 1, . . . , r. Since xp−(r−1)yp−(r−1) 6∈ E(H), it follows that xp−(r−1)bj0∈E(H), for if not, we find in Gthe path aj0, yp−(r−1), xp−(r−1), bj0 against our assumption. Analogously, ai0xp−(r−1) ∈E(H). Observe that {ai0xp−(r−1), ai0bi0} ⊂ E(Hp−r,p−r) and therefore, dHp−r,p−r(xp−(r−1)) = ∆X(Hp−r,p−r)≥dHp−r,p−r(ai0)≥2, which implies that dHi−1,i−1(xi)≥2 for i= 1, . . . , p −(r−1). Moreover, observe also that {yp−(r−1)bj0, aj0bj0} ⊂ E(Hp−r,p−(r+1)) and therefore, dHp−r,p−(r+1) (yp−r)=∆X(Hp−r,p−(r+1))≥dHp−r,p−(r+1) (bj0)≥2, which means that dHi,i−1(yi)≥2 for i= 1, . . . , p −r. Hence, e(H) = p−r X j=1 ¡dHj−1,j−1(xj) + dHj,j−1(yj)¢+¡dHp−r,p−r(xp−(r−1)) + dHp−(r−1),p−r(yp−(r−1))¢ + p X j=p−(r−2) ¡dHj−1,j−1(xj) + dHj,j−1(yj)¢+e(Hp,p) ≥4(p−r) + 3 + 2(r−1) + r = 4p+ 1 −r = 3p+1+(p−r) >3p+ 1, since r≤p−1. Then, if 2 ≤r≤p−1, in all the possible cases, we arrive at a contradiction with the assumption that the path ai, yp−(r−1), xp−(r−1), bidoes not exist in Gfor all i= 1, . . . , r. Thus, if 2≤r≤p−1 there exists i∈ {1, . . . , r}such that the path ai, yp−(r−1), xp−(r−1), biis contained in G. Without loss of generality we may assume that i=r. Then there exist in Gthe vertex-disjoint paths aj, yp−(j−1), xp−(j−1), bjfor j= 1, . . . , r. 16 Second, assume that r=p. Then, from Lemma 3.1 it follows that            {x1y1, . . . , xpyp} ∩ E(H) = ∅; {aiy2, . . . , aiyp} ∩ E(H) = ∅for i= 1, . . . , p; {x2bi, . . . , xpbi} ∩ E(H) = ∅for i= 1, . . . , p. (4) This means that for each i= 1, . . . , p and j= 0, . . . , p −2, there exists in Gthe path ai, yp−j, xp−j, bi. Thus, we only must show that there exists i∈ {1, . . . , p}such that the path ai, y1, x1, biis contained in G. We reason by way of contradiction supposing that for all i= 1, . . . , p the path ai, y1, x1, bidoes not exist in G. Since x1y1∈E(G) we deduce that for each i= 1, . . . , p,aiy1∈E(H) or x1bi∈E(H). If {aiy1, ai∗y1} ⊂ E(H) for two indices i, i∗∈ {1, . . . , p}, with i6=i∗, then dH1,0(y1)≥2. Since dH0,0(x1) = ∆X(H)≥2 we have e(H) = ¡dH0,0(x1) + dH1,0(y1)¢+ p X j=2 ¡dHj−1,j−1(xj) + dHj,j−1(yj)¢+e(Hp,p) ≥4 + 2(p−1) + p = 3p+ 2 >3p+ 1, a contradiction. Thus, in the set {a1, . . . , ap}there is at most one vertex adjacent to y1in H, which means that x1must be adjacent in Hto at least p−1 vertices of the set {b1, . . . , bp}, due to the fact that for each i= 1, . . . , p,aiy1∈E(H) or x1bi∈E(H). Then dH0,0(x1)≥p−1 and therefore, e(H) = ¡dH0,0(x1) + dH1,0(y1)¢+ p X j=2 ¡dHj−1,j−1(xj) + dHj,j−1(yj)¢+e(Hp,p) ≥p+ 2(p−1) + p = 3p+ 1 + (p−3) >3p+ 1, since p≥4, again a contradiction with the hypothesis. Hence, there exists i∈ {1, . . . , r}such that the path ai, yp−(r−1), xp−(r−1), biis contained in G. Without loss of generality we may assume that i=r. Then there exist in Gthe vertex-disjoint paths aj, yp−(j−1), xp−(j−1), bjfor j= 1, . . . , r, and the result holds. Theorem 3.1 Let m, n, s, t be integers such that 2≤s≤t,4≤m−s≤n−t, and m+n≤2s+t−1. 17 Then G= (X, Y )∈T Z(m, n;s, t)iff G=K(m,n)−Mwhere Mis any matching of cardinality 2(m−s) + n−t+ 1. Proof By Proposition 2.1 and Theorem 2.1, if G=K(m,n)−Mwhere Mis any matching of cardinality 2(m−s)+n−t+1, then G∈T Z(m, n;s, t). Thus, we only must show that there are no more extremal bipartite graphs. For that, it is enough to prove that the bipartite complement H= (X, Y ) of every extremal bipartite graph G= (X, Y )∈T Z(m, n;s, t) has maximum degree ∆(H) = 1. Let G= (X, Y )∈T Z(m, n;s, t) satisfy the hypothesis of the theorem and let us denote by H= (X, Y ) the bipartite complement of G. Set p=m−sand q=n−t, then 4 ≤p≤qand e(H)=2p+q+ 1. If p=qthen ∆(H) = 1, follows from Lemma 3.3. Thus, assume that p < q. Without loss of generality, we may assume that the vertices of the partite set Yare ordered in such a way that dH(y1)≥dH(y2)≥ · · · ≥ dH(yn). Set Y0={y1, . . . , yq−p} ⊆ Yand let us consider the bipartite graph H0= (X, Y \Y0). Observe that |X|=mand |Y\Y0|=n−(q−p) = t+p. If e(H0) = 0 then the bipartite complement G0of H0is the complete bipartite graph K(m,t+p). Since G0 is a subgraph of Gand K(s,t)⊆K(m,t+p), then Gcontains a K(s,t), against the assumption. So, we may assume that e(H0)>0, which means that dH(yi)≥1 for i= 1, . . . , q −p. Hence, e(H0) = e(H)− q−p X i=1 dH(yi)≤2p+q+ 1 −(q−p)≤3p+ 1.(5) Then the following facts can be concluded: •E(H0) = 3p+ 1. Otherwise if E(H0)<3p+ 1 then, from Lemma 2.3, it follows that G0 contains T K(m−p,n−(q−p)+p)=T K(m−p,n−q)=T K(s,t), but this contradicts the fact that G∈ T Z(m, n;s, t). •dH(yi) = 1, for i= 1, . . . , q −p, thus ∆Y(H) = 1, because ∆Y(H) = dH(y1). This is directly derived because all the inequalities (5) become equalities since E(H0) = 3p+ 1. Next let us see that ∆X(H) = 1. Otherwise, there is a vertex x∈Xhaving two distinct neighbors y, y∗∈NH(x). Since ∆Y(H) = 1, then NH(y) = NH(y∗) = {x}, and besides, there are exactly e(H) = 2p+q+ 1 > q −p+ 2 vertices of degree 1 in the class Y. Let us consider the bipartite graph G∗= (X∗, Y ∗) whose bipartite complement H∗= (X∗, Y ∗) is obtained from Hby removing any q−pvertices of Y\ {y, y∗}of degree 1. The graph H∗satisfies that |X∗|=|X|=m>p, |Y∗|=|Y| − (q−p) = t+p>p,e(H∗) = e(H)−(q−p) = 3p+ 1. Further, observe that dH∗(x)≥2, because {y, y∗} ⊂ Y∗and {xy, xy∗} ⊂ E(H∗), which means that ∆(H∗)≥2. Then, 18 by applying Lemma 3.3, the bipartite complement G∗of H∗contains a T K(m−p,t+p−p)=T K(s,t). Since G∗is a subgraph of G, we deduce that Gcontains T K(s,t), and this contradicts the fact that G∈T Z(m, n;s, t). Hence, ∆(H) = min{∆X(H),∆Y(H)}= 1 and this proves the result. Acknowledgments We would like to thank the anonymous referees for their suggestions and for their comments. This research was supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund (ERDF) under project MTM2008-06620-C03-02/MTM; also by Catalonian government 2009 SGR 1298; and under the Andalusian Government project P06-FQM-01649. References [1] Tur´an, P.: On an extremal problem in graph theory. Mat. Fiz. Lapok,48, 436–452 (1941). [2] Zarankiewicz, K.: Problem P 101. Colloq. Math.,2, 301 (1951). [3] Jung, H.A.: Eine Verallgemeinerung des n-fachen Zusammenhangs f¨ur Graphen. Math. Ann., 187, 95–103 (1970). [4] Bollob´as, B.: Extremal Graph Theory, Academic Press, New York, 1978. [5] M. Simonovits: Extremal graph theory, Selected topics in graph theory, 2, Academic Press, London, 1983, 161–200. [6] Fur¨edi, Z.: New asymptotics for Bipartite Tur´an Numbers. J. Combin. Theory Ser. A,75 141–144 (1996). [7] Godbole, A.P., Lamorte, B., Sandquist, E.J.: Threshold functions for the bipartite Tur´an property. Electron. J. Combin.,4, R18 (1997). [8] Bollob´as, B., Thomason, A.: Proof of a Conjecture of Mader, Erd¨os and Hajnal on Topological Complete Subgraphs. European J. Combin.,19, 883–887 (1998). [9] Mader, W.: 3n−5 edges do force a subdivision of K5,Combinatorica,18(4), 569–595 (1998). 19 [10] Goddard, W., Henning, M.A., Oellermann, O.R.: Bipartite Ramsey numbers and Zarankiewicz numbers. Discrete Math.,219, 85–95 (2000). [11] Luczak, T.: On triangle-free random graphs. Random Structures Algorithms,16(3), 260–276 (2000). [12] Godbole, A.P., Graziano, H.C.: Contributions to the problem of Zarankiewicz. J. Statist. Plann. Inference,95, 197–208 (2001). [13] Griggs, J., Chih-Chang, H.: On the half-half case of the Zarankiewicz problem. Discrete Math., 249, 95–104 (2002). [14] K¨uhn, D., Osthus, D.: Topological minors in graphs of large girth. J. Combin. Theory Ser. B, 86(2), 364–380 (2002). [15] Myers, J.S.: The extremal function for unbalanced bipartite minors. Discrete Math.,271, 209–222 (2003). [16] B¨ohme, T., Mohar, B., ˇ Skrekovski, R., Stiebitz, M.: Subdivisions of large complete bipartite graphs and long induced paths in k-connected graphs. J. Graph Theory,45, 270–274 (2004). [17] K¨uhn, D., Osthus, D.: Induced subdivisions in Ks,s-free graphs of large average degree. Combinatorica,24(2), 287–304 (2004). [18] Diestel, R.: Graph Theory, Springer-Verlag Berlin Heildeberg, 2005. [19] Mader, W.: Graphs with 3n−6 edges not containing a subdivision of K5.Combinatorica,25(4), 425–438 (2005). [20] K¨uhn, D., Osthus, D.: Improved bounds for topological cliques in graphs of large girth. SIAM J. Discrete Math.,20(1), 62–78 (2006). [21] Yan, J., Liu, G.Z.: On 2-factors with prescribed properties in a bipartite graph. Acta Math. Sin. (Engl. Ser.), 22(4), 1115-–1120 (2006). [22] Balbuena, C., Cera, M., Di´anez, A., Garc´ıa-V´azquez, P.: New exact values of the maximum size of graphs free of topological complete subgraphs. Discrete Math.,307(9-10), 1038–1046 (2007). [23] Balbuena, C., Garc´ıa-V´azquez, P., Marcote, X., Valenzuela, J.C.: New results on the Zarankiewicz problem. Discrete Math.,307(17-18), 2322–2327 (2007). 20 [24] Shiu, W.C., Liu, G.Z.: k-factors in regular graphs. Acta Math. Sin. (Engl. Ser.),24(7), 1213–1220 (2008). [25] Liu, Y., Yan, G.Y.: Graphs isomorphic to their maximum matching graphs. Acta Math. Sin. (Engl. Ser.),29(9), 1507–1516 (2009). [26] Liu, Y., Yan, G.Y.: Graphs isomorphic to their maximum matching graphs. Acta Math. Sin. (Engl. Ser.),29(9), 1507–1516 (2009). [27] Volkmann, L., Zingsem, A.: Smallest close to regular bipartite graphs without an almost perfect matching. Acta Math. Sin. (Engl. Ser.),26(8), 1403–1412 (2010). [28] Fan, H.B., Liu, G.Z., Liu, J.P., Long, H.P.: The existence of even regular factors of regular graphs on the number of cut edges. Acta Math. Sin. (Engl. Ser.),26(12), 2305–2312 (2010). 21