Topological minors in bipartite graphs |
| |
| Authors: | Camino Balbuena Martín Cera Pedro García-Vázquez Juan Carlos Valenzuela |
| |
| Affiliation: | 1.Departament de Matemàtica Aplicada III,Universitat Politècnica de Catalunya,Barcelona,Spain;2.Departamento de Matemática Aplicada I,Universidad de Sevilla, EUIT Agrícola,Sevilla,Spain;3.Departamento de Matemática Aplicada I,Universidad de Sevilla, ETS Arquitectura,Sevilla,Spain;4.Departamento de Matemáticas,Universidad de Cádiz, EPS Algeciras,Algeciras,Spain |
| |
| Abstract: | 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. |
| |
| Keywords: | Bipartite graphs extremal graph theory topological minor |
| 本文献已被 维普 SpringerLink 等数据库收录！ |
|
