標題: The decycling number of outerplanar graphs
作者: Chang, Huilan
Fu, Hung-Lin
Lien, Min-Yun
應用數學系
Department of Applied Mathematics
關鍵字: Decycling number;Feedback vertex number;Cycle packing number;Outerplanar graph
公開日期: 1-May-2013
摘要: For a graph G, let tau(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)a parts per thousand currency sign tau(G)a parts per thousand currency sign2c(G) for an outerplanar graph G. An outerplanar graph G is called lower-extremal if tau(G)=c(G) and upper-extremal if tau(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 of outerplanar graphs none of which is lower-extremal and show that if G has no subdivision of S for all , then G is lower-extremal.
URI: http://dx.doi.org/10.1007/s10878-012-9455-1
http://hdl.handle.net/11536/21647
ISSN: 1382-6905
DOI: 10.1007/s10878-012-9455-1
期刊: JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume: 25
Issue: 4
起始頁: 536
結束頁: 542
Appears in Collections:Articles


Files in This Item:

  1. 000317973700005.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.