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全文 |