The arboricity of graph G=(V,E), denoted by a(G), is defined as a(G)=min{n | E can be partitioned into n subsets E1,E2,...,En, such that each subset spans a subgraph of G so as to be a forest}.In this paper the follow...The arboricity of graph G=(V,E), denoted by a(G), is defined as a(G)=min{n | E can be partitioned into n subsets E1,E2,...,En, such that each subset spans a subgraph of G so as to be a forest}.In this paper the following results have been obtained. For any graph G of order p,and the bounds are sharp; especially as an integer function, 5p+7 could not be decreased. Furthermore, Nordhaus-Gaddum Theorem for arboricity has also been got.展开更多
文摘The arboricity of graph G=(V,E), denoted by a(G), is defined as a(G)=min{n | E can be partitioned into n subsets E1,E2,...,En, such that each subset spans a subgraph of G so as to be a forest}.In this paper the following results have been obtained. For any graph G of order p,and the bounds are sharp; especially as an integer function, 5p+7 could not be decreased. Furthermore, Nordhaus-Gaddum Theorem for arboricity has also been got.
