Linear Arboricity of Regular Digraphs

(整期优先)网络出版时间:2017-04-14
/ 1
Alineardirectedforestisadirectedgraphinwhicheverycomponentisadirectedpath.Thelineararboricityla(D)ofadigraphDistheminimumnumberoflineardirectedforestsinDwhoseunioncoversallarcsofD.Foreveryd-regulardigraphD,NakayamaandPerocheconjecturethatla(D)=d+1.Inthispaper,weconsiderthelineararboricityforcompletesymmetricdigraphs,regulardigraphswithhighdirectedgirthandrandomregulardigraphsandweimprovesomewell-knownresults.