The Vertex Arboricity Of Square Graphs

All graphs considered in this paper are finite,loopless,and without multiple edges.For a graph G,let V(G),E(G),|G|,Δ(G),andδ(G) denote,respectively: its vertex set,edge set,number of vertices,maximum degree,and minimum degree. Let dG(x) denotes the degree of the vertex x. Let G be a graph,a k coloringσof G is an injection from V(G) to {1,2,..., k}.The vertex arboricity va(G) is the minimum number of subsets into which the set of vertices of G can be partitioned such that each subset induces a forest.For any 3-connected planar graph G(V, E, F) withδ(G)≥3,if the boundary edges of face f0 which is adjacent to the others are removed,it becomes a tree,and the degree of each vertex of V(f0) is 3,and then G is called a Halin graph; f0 is called the outer face of G,and the others called the interior faces; the vertices on the face f0 are called the outer vertices,the others are called the interior vertices.Let u,υbe two vertices of G,the distance between u andυ,denoted by dG(u,υ),is the length of the smallest path between u andυ.The square graph G2 of a graph G is the graph defined on the vertex set V(G) such that two vertices u andυare adjacent in G2 if and only if 1≤dG(u,υ)≤2.We introduce the defined of some arboricity and some main results,and we give the vertex arboricity of the square of Halin graph in this paper.In chapter 1,we collect some basic notions used in the thesis and give a chief survey on this direction.Main results in the thesis are stated.In chapter 2,we introduce the defined of some arboricity and some main re-sults, including some arboricity about vertex:vertex arboricity,vertex linear arboricity,vertex star arboricity,and including some arboricity about edge:edge arboricity,linear arboricity,catepillar arboricity,star arboricity,T—free ar-boricity,Sn—free arboricity,Pn—free arboricity,K1,n—free arboricity.We also introduce some results about arboricity.In chapter 3,we study the arboricity of the square of Halin graph. Arboricity of planar graphs have been extensively investigated in the past years,but few results have been known about the arboricity of non-planar graphs.Generally speaking,the square of Halin graph is a non-planar graph. A. F.Yang and J. J. Yuan have proofed that the induced forest 2-partition problem for graphs of diameter 2 is NP-complete,so the problem of vertex arboricity of graph is NP-complete. G.Ma in Shandong university has proofed that the vertex arboricity of the square of tree is [Δ+1/2].We will study the vertex arboricity of the square of Halin graph in this chapter.There are two results:Theorem 3.2.5. For Halin graph G,ifΔ(G)< 6,then the vertex arboricity of the square of G satisfy 2≤υa(G)≤4.Theorem 3.2.7. For Halin graph G,if the degrees of all the interior vertices are greater or equal to 6,then the vertex arboricity of the square of G is[Δ+1/2].