標題: Vertex and tree arboricities of graphs
作者: Chang, GJ
Chen, CY
Chen, YP
應用數學系
Department of Applied Mathematics
關鍵字: arboricity;acyclic;tree;block-cactus graph;series-parallel graph;cograph;girth;planar graph;hamiltonian cycle
公開日期: 1-Sep-2004
摘要: 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.
URI: http://dx.doi.org/10.1023/B:JOCO.0000038912.82046.17
http://hdl.handle.net/11536/26385
ISSN: 1382-6905
DOI: 10.1023/B:JOCO.0000038912.82046.17
期刊: JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume: 8
Issue: 3
起始頁: 295
結束頁: 306
Appears in Collections:Articles


Files in This Item:

  1. 000223483800004.pdf