Linear Arboricity of Regular Digraphs

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 Dwhose union covers all arcs of D. For every d-regular digraph D, Nakayama and Peroche conjecturethat la（D） = d ＋ 1....

Full description

Saved in:
Bibliographic Details
Published in:Acta mathematica Sinica. English series 2017-04, Vol.33 (4), p.501-508
Main Authors: He, Wei Hua, Li, Hao, Bai, Yan Dong, Sun, Qiang
Format: Article
Language:English
Subjects:
arboricity
Combinatorics
Computer Science
Decomposition
digraph
digraphs
Discrete Mathematics
Forests
Graph theory
Lemma
Linear
Local
Lovasz
Mathematical analysis
Mathematics
Mathematics and Statistics
random
regular
Studies
Symmetry
Unions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Dwhose union covers all arcs of D. For every d-regular digraph D, Nakayama and Peroche conjecturethat 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.
ISSN:1439-8516
1439-7617
DOI:10.1007/s10114-016-5071-9