Article
Topological minors in bipartite graphs
Author/s | Balbuena, Camino
Cera López, Martín García Vázquez, Pedro Valenzuela, Juan Carlos |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada |
Publication Date | 2011-10-15 |
Deposit Date | 2024-01-29 |
Published in |
|
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) ... 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. |
Citation | Balbuena, C., Cera López, M., García Vázquez, P. y Valenzuela, J.C. (2011). Topological minors in bipartite graphs. Acta Mathematica Sinica, 27, 2085-2100. https://doi.org/10.1007/s10114-011-0149-x. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Trabajo 1 Aceptada Sinica.pdf | 211.4Kb | [PDF] | View/ | |