Some Extremal Problems On Digraphs

Extremal graph theory is an important branch of graph theory.It concerns the relations between parameters such as the number of edges,the number of vertices,the maximum degree,the minimum degree,girth,as well as the values of parameters of the graphs with special properties.We investigate several Turán type problems on digraphs.We present the exact Turán numbers for some digraphs and characterize the corresponding extremal digraphs.Our main results are as follows.(1)We determine the maximum size of a digraph of order n avoiding two distinct walks of length k with the same endpoints when k≥ 4 and n≥ k+4.The extremal digraphs are also characterized when k≥ 5 and n≥ k+2.(2)We determine the maximum size of a digraph of order n avoiding two distinct walks of length 2 with the same endpoints as well as the extremal digraphs when n>8.(3)We determine the maximum number of arcs in the digraphs of order n avoiding t+1 distinct walks of length k with the same endpoints.We also characterize the extremal digraphs when k≥ n-1 and n is sufficiently large.(4)We determine the maximum number of arcs in the P2,2-free digraphs of order n and the extremal digraphs when n>13,where P2,2 is the union of two distinct paths with the same endpoints.(5)We determine the maximum number of arcs in the digraphs on n vertices avoiding the orientation H of the diamond and the extremal digraphs when n≥ 16,where H is the digraphs with vertex set {1,2,3,4} and arc set{12,13,24,34,14}.