Cycle Covers of Planar 2-Edge-Connected Graphs |
| |
Authors: | D. W. Barnette |
| |
Affiliation: | 1. Department of Mathematics, University of California, Davis, CA, 95616, USA
|
| |
Abstract: | A graph with n vertices is said to have a small cycle cover provided its edges can be covered with at most (2n ? 1)/3 cycles. Bondy [2] has conjectured that every 2-connected graph has a small cycle cover. In [3] Lai and Lai prove Bondy’s conjecture for plane triangulations. In [1] the author extends this result to all planar 3-connected graphs, by proving that they can be covered by at most (n + 1)/2 cycles. In this paper we show that Bondy’s conjecture holds for all planar 2-connected graphs. We also show that all planar 2-edge-connected graphs can be covered by at most (3n ? 3)/4 cycles and we show an infinite family of graphs for which this bound is attained. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|