Subgraphs with Restricted Degrees of Their Vertices in Planar 3-Connected Graphs |
| |
Authors: | Igor Fabrici Stanislav Jendrol |
| |
Institution: | 1. Institute of Mathematics, Technical University Ilmenau, PF 0565, D-98684, Ilmenau, Germany 2. Department of Geometry and Algebra, P.J. ?afárik University, Jesenná 5, 041 54, Kos?ice, Slovak Republic
|
| |
Abstract: | We have proved that every 3-connected planar graph G either contains a path on k vertices each of which has degree at most 5k or does not contain any path on k vertices; the bound 5k is the best possible. Moreover, for every connected planar graph H other than a path and for every integer m ≥ 3 there is a 3-connected planar graph G such that each copy of H in G contains a vertex of degree at least m. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|