| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4949559 | Discrete Applied Mathematics | 2017 | 7 Pages |
Abstract
A P3â-decomposition of a directed graph D is a partition of the arcs of D into directed paths of length 2. We characterize symmetric digraphs that do not admit a P3â-decomposition. We show that the only 2-regular, connected directed graphs that do not admit a P3â-decomposition are obtained from undirected odd cycles by replacing each edge by two oppositely directed arcs. In both cases, we give a linear-time algorithm to find a P3â-decomposition, if it exists.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ajit A. Diwan,