标题: | 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-五月-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 |
显示于类别: | Articles |
文件中的档案:
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.