Vertex and Tree Arboricities of Graphs |
| |
| Authors: | Gerard J Chang Chiuyuan Chen Yaping Chen |
| |
| Institution: | (1) Department of Mathematics, National Taiwan University, Taipei, 106, Taiwan.;(2) Department of Applied Mathematics, National Chiao Tung University, Hsinchu, 300, Taiwan. |
| |
| Abstract: | 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. |
| |
| Keywords: | arboricity acyclic tree block-cactus graph series-parallel graph cograph girth planar graph hamiltonian cycle |
| 本文献已被 SpringerLink 等数据库收录！ |
|
