Judicious Multipart Partitions Of Directed Graphs

The vertex partition problem of graphs is a hot topic in extreme graph theory,which includes the max cut problem and various judicious partition problems.Judicious partition problems of undirected graphs have been widely concerned.However,the research of judicious partitions of directed graphs is just beginning,and mainly focuses on bipartition problems.This thesis will study the problem of judicious multipartite partitions of directed graphs.Chapter 1 mainly introduces the research background and related concepts of the judicious partitions of undirected and directed graphs.The problem of judicious bipartitions of directed graphs is generalized and the following problems are proposed:(1)The judicious multipartite partition problem of vertex set pair type:Given an integer k≥ 2 and a directed graph D=(V,E),ask for a k-partition of the vertex set V(D)=V1 ∪ V2 ∪…∪ Vk,such that min{e(Vi,Vj):i,j∈{1,2,…,k} and i≠j} is maximal,where e(Vi,Vj)is the number of directed edges from Vi to Vj.(2)The judicious multipartite partition problem of out-arc type:Given an integer k≥ 2 and a directed graph D=(V,E),ask for a k-partition of the vertex set V(D)=V1 ∪ V2 ∪…∪ Vk,such that min{e+(Vi):i ∈ {1,2,…,k}} is maximal,where e+(Vi)is the number of directed edges leaving from Vi.In Chapter 2,we study the judicious multipartite partition problem of vertex set pair types.Firstly,the problem of judicious k-partitions of a directed graph is studied by a randomized algorithm,and it is proved that for any e>0 and directed graph D=(V,E)with n vertices and m edges,if maxv∈V d(v)≤ ε2/2k(k-1)m or m≥4ε-2nk(k-1),there is a partition of the vertex set V(D)=V1 ∪ V2 ∪…∪ VK such that min{e(Vi,Vj):i,j ∈{1,2,…,k} and i≠j}≥(1/k2-ε)m;Secondly,using the Hoeffding-Azuma inequality and an important conclusion on the decomposition of undirected graphs given by Lee,Loh,and Sudakov,the above result is improved on some graph classes.Finally,we study the problem of judicious 3-partitions of directed graphs satisfying a minimum degree condition,and prove that for any ε>0,there is a positive integer n0,so that every directed graph with n≥ n0 vertices,m edges and minimum degree d>60 has a 3-partition V(D)=V1∪V2∪V3 satisfying min{e(V1,V2),e(V2,V1),e(V1,V3),e(V3,V1),e(V2,V3),e(V3,V2)≥(1/12-ε)m.In Chapter 3,we study the judicious multipartite partition problem of out-arc type.Similar to the research in Chapter 2,it is proved that for any ε>0 and directed graph D=(V,E)with n vertices and m edges,if maxv∈Bd(v)≤ε2/2k(k-1)m≥ 4k(k-1)ε-2n,then there is a partition of the vertex set V(D)=V1 ∪ V2 ∪…∪ Vk such that min{e+(Vi):i∈{1,2,…,k}}≥(k-1/k2-ε)m.Also,using techniques such as Hoeffding-Azuma inequality,we prove that for any ε>0,there is a positive integer n0,so that each directed graph with n≥ n0 vertices,m edges and minimum degree d≥16 has a 3-partition V(D)=V1 ∪ V2 ∪ V3 satisfying min{e+(V1),e+(V2),e+(V3)}≥(1/6-ε)m.