Vertex and tree arboricities of graphs
檔案
- 000223483800004.pdf (129.0 KB, Adobe PDF)
日期
2004-09-01
類型
系所
期刊名稱
JOURNAL OF COMBINATORIAL OPTIMIZATION
卷期與頁次
第 8 卷第 3 期,頁 295–306
ISSN
1382-6905
語言
英文
摘要
This paper studies the following variations of arboricity of graphs. The vertex ( respectively, tree) arboricity of a graph G is the minimum number va( G) ( respectively, ta( G)) of subsets into which the vertices of G can be partitioned so that each subset induces a forest ( respectively, tree). This paper studies the vertex and the tree arboricities on various classes of graphs for exact values, algorithms, bounds, hamiltonicity and NP-completeness. The graphs investigated in this paper include block-cactus graphs, series-parallel graphs, cographs and planar graphs.