Premium
Linear arboricity of digraphs
Author(s) -
Nakayama A.,
Peroche B.
Publication year - 1987
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230170104
Subject(s) - arboricity , digraph , partition (number theory) , combinatorics , mathematics , degeneracy (biology) , time complexity , strongly connected component , discrete mathematics , graph , planar graph , biology , genetics
A linear diforest is a digraph whose connected components are paths. We define the linear arboricity of a digraph, denoted la(G) , as the minimum number of linear diforests which partition the arcs of G. In this paper, we prove that the determination of la(G) is NP‐complete. We prove also that the problem becomes polynomial for acyclic digraphs. Finally, we give the value of la(G) for several families of digraphs, in particular 2‐regular digraphs.