Abstract
For a graph G, let τ(G) be the decycling number of G and c(G) be the number of vertex-disjoint cycles of G. It has been proved that c(G)≤τ(G)≤2c(G) for an outerplanar graph G. An outerplanar graph G is called lower-extremal if τ(G)=c(G) and upper-extremal if τ(G)=2c(G). In this paper, we provide a necessary and sufficient condition for an outerplanar graph being upper-extremal. On the other hand, we find a class S of outerplanar graphs none of which is lower-extremal and show that if G has no subdivision of S for all S ε S, then G is lower-extremal.
Original language | English |
---|---|
Pages (from-to) | 536-542 |
Number of pages | 7 |
Journal | Journal of Combinatorial Optimization |
Volume | 25 |
Issue number | 4 |
DOIs | |
State | Published - 1 May 2013 |
Keywords
- Cycle packing number
- Decycling number
- Feedback vertex number
- Outerplanar graph