Topological Minors in Bipartite Graphs

被引:0
作者
Balbuena, Camino [1 ]
Cera, Martin [2 ]
Garcia-Vazquez, Pedro [3 ]
Carlos Valenzuela, Juan [4 ]
机构
[1] Univ Politecn Cataluna, Dept Matemat Aplicada 3, ES-08034 Barcelona, Spain
[2] Univ Seville, Dept Matemat Aplicada 1, EUIT Agr, Seville 41013, Spain
[3] Univ Seville, Dept Matemat Aplicada 1, ETS Arquitectura, E-41012 Seville, Spain
[4] Univ Cadiz, Dept Matemat, EPS Algeciras, Algeciras 11202, Spain
关键词
Bipartite graphs; extremal graph theory; topological minor; ZARANKIEWICZ PROBLEM; COMPLETE SUBGRAPHS; REGULAR GRAPHS; LARGE GIRTH; EDGES; SUBDIVISIONS; NUMBERS;
D O I
10.1007/s10114-011-0149-x
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s and t such that 2 <= s <= t, 0 <= m - s <= n - t, and m + 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.
引用
收藏
页码:2085 / 2100
页数:16
相关论文
共 27 条
  • [1] New results on the Zarankiewicz problem
    Balbuena, C.
    Garcia-Vazquez, P.
    Marcote, X.
    Valenzuela, J. C.
    [J]. DISCRETE MATHEMATICS, 2007, 307 (17-18) : 2322 - 2327
  • [2] New exact values of the maximum size of graphs free of topological complete subgraphs
    Balbuena, C.
    Cera, M.
    Dianez, A.
    Garcia-Vazquez, P.
    [J]. DISCRETE MATHEMATICS, 2007, 307 (9-10) : 1038 - 1046
  • [3] Subdivisions of large complete bipartite graphs and long induced paths in k-connected graphs
    Böhme, T
    Mohar, B
    Skrekovski, R
    Stiebitz, M
    [J]. JOURNAL OF GRAPH THEORY, 2004, 45 (04) : 270 - 274
  • [4] Proof of a conjecture of Mader, Erdos and Hajnal on topological complete subgraphs
    Bollobás, B
    Thomason, A
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 1998, 19 (08) : 883 - 887
  • [5] Bollobas B., 2004, Extremal Graph Theory
  • [6] Diestel R., 2005, GRAPH THEORY, VThird
  • [7] The existence of even regular factors of regular graphs on the number of cut edges
    Fan, Hong Bing
    Liu, Gui Zhen
    Liu, Ji Ping
    Long, He Ping
    [J]. ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2010, 26 (12) : 2305 - 2312
  • [8] New asymptotics for bipartite Turan numbers
    Furedi, Z
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 1996, 75 (01) : 141 - 144
  • [9] Godbole AP, 2001, J STAT PLAN INFER, V95, P197
  • [10] GODBOLE AP, 1997, ELECTRON J COMB, V4, pR18