Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2209.08944 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908903491502080 |
|---|---|
| author | Hajac, Piotr M. Stachowiak, Oskar M. |
| author_facet | Hajac, Piotr M. Stachowiak, Oskar M. |
| contents | We consider the class of directed graphs with $N\geq 1$ edges and without loops shorter than $k\geq1$. Using the concept of a labelled graph, we determine graphs from this class that maximize the number of all 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\geq1$ edges. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_08944 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Counting paths in directed graphs Hajac, Piotr M. Stachowiak, Oskar M. Combinatorics 05C30 We consider the class of directed graphs with $N\geq 1$ edges and without loops shorter than $k\geq1$. Using the concept of a labelled graph, we determine graphs from this class that maximize the number of all 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\geq1$ edges. |
| title | Counting paths in directed graphs |
| topic | Combinatorics 05C30 |
| url | https://arxiv.org/abs/2209.08944 |