Topological Minors in Bipartite Graphs  

作　　者：Camino BALBUENA Martin CERA Pedro GARCIA-VAZQUEZ Juan Carlos VALENZUELA 

机构地区：[1]Departament de Matematica Aplicada III, Universitat Politecnica de Catalunya, C/ Jordi Girona 1-3 （ Edifici C2, Despatx 302）, 08034 Barcelona, Spain [2]Departamento de Matemdtica Aplicada I, Universidad de SeviUa, EUIT Agrlcola, Ctra. Utrera, Kin. 1, 41013 Sevilla, Spain [3]Departamento de Matemdtica Aplicada I, Universidad de Sevilla, ETS Arquitectura, Avda. Reina Mercedes, 2, 41012 Sevilla, Spain [4]Departamento de Matemdticas, Universidad de Cddiz, EPS Algeciras, Avda. Ramdn Puyol, s/n, 11202 Algeciras, Spain

出　　处：《Acta Mathematica Sinica,English Series》2011年第11期2085-2100,共16页数学学报（英文版）

摘　　要：For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s andt such that 2≤ s ≤ t, 0≤ m-s ≤ n-t, andre＋n≤ 2s＋t-1, we prove that if G has at least mn- （2（m - s） ＋ n - t） edges then it contains a subdivision of the complete bipartite K（s,t） with s vertices in the m-class and t vertices 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.For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s andt such that 2≤ s ≤ t, 0≤ m-s ≤ n-t, andre＋n≤ 2s＋t-1, we prove that if G has at least mn- （2（m - s） ＋ n - t） edges then it contains a subdivision of the complete bipartite K（s,t） with s vertices in the m-class and t vertices 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.

关 键 词：Bipartite graphs extremal graph theory topological minor 

分 类 号：O157.5[理学—数学] TP393[理学—基础数学]