Counting paths in directed graphs
Bulletin of the Polish Academy of Sciences. Mathematics · 20.03.2026
DOI: 10.4064/ba250507-22-12 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bulletin of the Polish Academy of Sciences. Mathematics, online erschienen am 20.03.2026. Verfasst von Piotr M. Hajac und 1 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
Hajac, P. M., & Stachowiak, O. M. (2026). Counting paths in directed graphs. Bulletin of the Polish Academy of Sciences. Mathematics. https://doi.org/10.4064/ba250507-22-12
Vancouver
Hajac PM, Stachowiak OM. Counting paths in directed graphs. Bulletin of the Polish Academy of Sciences. Mathematics. 2026. doi:10.4064/ba250507-22-12
BibTeX
@article{Hajac2026,
author = {Hajac, Piotr M. and Stachowiak, Oskar M.},
title = {Counting paths in directed graphs},
journal = {Bulletin of the Polish Academy of Sciences. Mathematics},
year = {2026},
doi = {10.4064/ba250507-22-12}
}
EUVIMED