Partitions of digraphs into paths or circuits
type: Item
instance of: scholarly article
title: Partitions of digraphs into paths or circuits
zbMATH Open document ID: 0605.05016
DOI: 10.1016/0012-365X(86)90106-8
published in: Discrete Mathematics
publication date: 1986-01-01T00:00:00Z
review text: The paper considers the problem of partitioning the arcs of a digraph into elementary paths or circuits. It is conjectured that the arcs of a digraph can be partitioned into \(\alpha\) or fewer elementary paths or circuits where \(\alpha\) is the minimum number of a demi-cocycle. It is shown that the arcs of a pseudo-symmetric digraph or an acircuitous digraph can be partitioned into \(\alpha\) or fewer circuits. Furthermore, the arcs of a bipartite digraph can be partitioned into \(\alpha\) paths or circuits of length at most two and this bound is the best possible.
reviewed by: Wai-Kai Chen
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 3977028
zbMATH Keywords: arc partition
zbMATH Keywords: graph decomposition
zbMATH Keywords: paths
zbMATH Keywords: circuits
author: Wojciech Bienia
author: Henri Meyniel
MaRDI profile type: Publication
cites work: Path numbers of tournaments
cites work: Path decompositions of digraphs
cites work: Q5615282
cites work: An upper bound on the path number of a digraph
Recommended article: Q4817890
Recommended article: Q3765803
Recommended article: On the path partition of graphs
Recommended article: Partition and disjoint cycles in digraphs
Recommended article: Graph partition problems into cycles and paths
Recommended article: Partitions of Graphs
Recommended article: Partitioning graphs into paths or cycles of prescribed lengths
Recommended article: Path partitions and packs of acyclic digraphs
Recommended article: Path partitions of planar graphs
Recommended article: Q3166152
description: scientific article; zbMATH DE number 3977028