首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Linear arboricity of regular digraphs
Authors:Wei Hua He  Hao Li  Yan Dong Bai  Qiang Sun
Institution:1.Department of Applied Mathematics, Guangdong University of Technology, Guangzhou 510006, P. R. China;2.Laboratoire de Recherche en Informatique, UMR 8623, C.N.R.S.-Université de Paris-sud, 91405-Orsay cedex, France
Abstract:A linear directed forest is a directed graph in which every component is a directed path. The linear arboricity la(D) of a digraph D is the minimum number of linear directed forests in D whose union covers all arcs of D. For every d-regular digraph D, Nakayama and Péroche conjecture that la(D) = d + 1. In this paper, we consider the linear arboricity for complete symmetric digraphs, regular digraphs with high directed girth and random regular digraphs and we improve some well-known results. Moreover, we propose a more precise conjecture about the linear arboricity for regular digraphs.
Keywords:Linear arboricity  digraph  Lová  sz Local Lemma  random regular digraphs  
本文献已被 CNKI SpringerLink 等数据库收录!
点击此处可从《数学学报(英文版)》浏览原始摘要信息
点击此处可从《数学学报(英文版)》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号