A (?) Decomposition Of Tournaments And Bipartite Digraphs

A decomposition of a graph G =(V(G),E(G))is family F of edge-disjoint subgraphs of G =(V(G),-E(G))such that UF?fE(F)= E(G).If F consists entirely of paths or entirely of cycles,it is called a path decomposition or cycle decomposition of G.In addition,if f = {F} for a single graph F,we simply write F-decomposition of G.Veblen[18]proved that a graph admits a cycle decomposition if and only if all vertices of the graph have even degrees.There are a large amount of literatures which are concerned with various kinds of decompositions of graphs,see[3]for some definitions,conceptions and earlier results.For an integer k?2,a Pk-decomposition of a graph G is a partition of the edge set of G into paths of length k-1.The same notion of decomposition applies to directed graphs as well,a decomposition of a graph D =(V(D),A(D))is family F of arc-disjoint subgraphs of D =(V(D),A(D))such that UF?FA(F)= A(D).A (?)decomposition of a directed graph D is a partition of the arcs of D into directed paths of length k-1.In particular,a (?)-decomposition of a directed graph D is a partition of the arcs of D into directed paths of length 2.Thomassen[13-15]investigated the Pk-decomposition of graphs when k? 4.How-ever,no characterization of directed graphs that admit a (?)-decomposition is known in general.Very recently,Diwan[5]initiates the study of (?)-decomposition a directed graph.In this paper,we give a complete characterization for a digraph admitting a,(?)-decomposition.This solves a problem posed by Diwan.