Some Problems On Linear Arboricity Of Digraphs

A linear k-diforest is a directed forest in which every connected component is a directed path of length at most k.The linear k-arboricity of a digraph D is the minimum number of linear k-diforests needed to partition the arcs of D.In this paper,we mainly study the linear k-arboricity of some special classes of digraphs.In Chapter 1,we introduce the definitions of linear arboricity and linear k-arboricity,then introduce the related results at home and abroad and main results of this paper.In Chapter 2,we introduce two families of symmetric directed trees and characterize them,then introduce ?(T*)-critical tree with linear 2-arboricity of ?(T*)+1.We also get the value range of linear 2-arboricity of symmetric directed tree.Finally,the necessary and sufficient conditions for the linear 2-arboricity of symmetric directed trees are proved and the results are extended to the linear k-arboricity of symmetric directed trees.In Chapter 3 and 4,we study the linear 2-arboricity and linear 3-arboricity for symmetric complete digraphs and symmetric complete bipartite digraphs.By applying similar partitioning methods in undirected graphs,we get the exact values of them.