Partition of graphs with condition on the connectivity and minimum degree |
| |
Authors: | Péter Hajnal |
| |
Institution: | (1) Bolyai Institute of A. József University, Aradi vértanúk t. 1, H-6720 Szeged, Hungary |
| |
Abstract: | C. Thomassen and M. Szegedy proved the existence of a functionf(s, t) such that the points of anyf(s, t)-connected graph have a decomposition into two non-empty sets such that the subgraphs induced by them ares-connected andt-connected, respectively. We prove, thatf(s, t) ≦ 4s+4t − 13 and examine a similar problem for the minimum degree. |
| |
Keywords: | 05 C 40 |
本文献已被 SpringerLink 等数据库收录! |
|