A $\overrightarrow{P_3}$-decomposition of tournaments and bipartite digraphs

Abstract

A $\overrightarrow{P_3}$-decomposition of a directed graph $D$ is a partition of the arcs of $D$ into directed paths of length $2$. In this paper, we give a characterization for a tournament and a bipartite digraph admitting a $\overrightarrow{P_3}$-decomposition. This solves a problem posed by Diwan ($\overrightarrow{P_3}$-decomposition of directed graphs, Discrete Appl. Math., http:// dx.doi.org/10.1016/j.dam.2016.01.039.).

12 pages, 3 figures