Line digraphs of polytrees
We characterize line digraphs of polytrees, including several of their well-known subclasses. For a given undirected tree, we characterize its orientations with weak line digraphs, and count the exact number. Furthermore, we find the minimum, maximum, and average sizes of these line digraphs. We provide an explicit formula for the number of weak components in line digraphs of polytrees in terms of the inner sources and sinks. Additionally, we count the average number of weak components in them among all orientations of a fixed tree. Finally, we propose an algorithm for finding weak components in line digraphs of polytrees.
Publication Details
- Journal
- Utilitas Mathematica
- Published
- 2025-09-27
- DOI
- https://doi.org/10.61091/um124-01
- Primary Topic
- Protein Kinase Regulation and GTPase Signaling
- Type
- article
- Field-Weighted Citation Impact
- 0.00