On Light Graphs in 3-Connected Plane Graphs Without Triangular or Quadrangular Faces |
| |
Authors: | Stanislav Jendrol' Peter J Owens |
| |
Institution: | (1) Department of Geometry and Algebra, P. J. Šafárik University, Jesenná 5, 041 54 Košice, Slovakia. e-mail: jendrol@kosice.upjs.sk, SK;(2) Department of Mathematics and Statistics, University of Surrey, Guildford, Surrey GU2 5XH, England, GB |
| |
Abstract: | We prove that each 3-connected plane graph G without triangular or quadrangular faces either contains a k-path P
k
, a path on k vertices, such that each of its k vertices has degree ≤5/3k in G or does not contain any k-path. We also prove that each 3-connected pentagonal plane graph G which has a k-cycle, a cycle on k vertices, k∈ {5,8,11,14}, contains a k-cycle such that all its vertices have, in G, bounded degrees. Moreover, for all integers k and m, k≥ 3, k∉ {5,8,11,14} and m≥ 3, we present a graph in which every k-cycle contains a vertex of degree at least m.
Received: June 29, 1998 Final version received: April 11, 2000 |
| |
Keywords: | , ,3-Connected plane graphs, Light graphs, Trianglefree and quadranglefree plane graphs |
本文献已被 SpringerLink 等数据库收录! |
|