The decycling number of outerplanar graphs

Huilan Chang*, Hung-Lin Fu, Min Yun Lien

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 languageEnglish
Pages (from-to)536-542
Number of pages7
JournalJournal of Combinatorial Optimization
Volume25
Issue number4
DOIs
StatePublished - 1 May 2013

Keywords

  • Cycle packing number
  • Decycling number
  • Feedback vertex number
  • Outerplanar graph

Fingerprint Dive into the research topics of 'The decycling number of outerplanar graphs'. Together they form a unique fingerprint.

Cite this