Counting paths in directed graphs
Abstract
We consider the class of directed graphs with N≥1 edges and without loops shorter than k≥1. Using the concept of a labelled graph, we determine graphs from this class that maximize the number of paths of length k. Then we show an R-labelled version of this result for semirings R contained in the semiring of non-negative real numbers and containing the semiring of non-negative rational numbers. We end by posing a related open problem concerning the maximal dimension of the path algebra of a connected acyclic directed graph with N≥1 edges.
Fields of Study & Subjects
Computability
Logic
AI Algorithms
semigroups and automata theory
Polynomial and algebraic computation
Publication details
- Journal / source
- Bulletin of the Polish Academy of Sciences Mathematics
- Publisher
- Institute of Mathematics, Polish Academy of Sciences
- Publication date
- 20 March 2026
- Language
- EN