A note on connectivity in directed graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909319261323264 |
|---|---|
| author | Stylianou, Stelios |
| author_facet | Stylianou, Stelios |
| contents | We say a directed graph $G$ on $n$ vertices is irredundant if the removal of any edge reduces the number of ordered pairs of distinct vertices $(u,v)$ such that there exists a directed path from $u$ to $v$. We determine the maximum possible number of edges such a graph can have, for every $n \in \mathbb{N}$. We also characterize the cases of equality. This resolves, in a strong form, a question of Crane and Russell. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_12137 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A note on connectivity in directed graphs Stylianou, Stelios Combinatorics We say a directed graph $G$ on $n$ vertices is irredundant if the removal of any edge reduces the number of ordered pairs of distinct vertices $(u,v)$ such that there exists a directed path from $u$ to $v$. We determine the maximum possible number of edges such a graph can have, for every $n \in \mathbb{N}$. We also characterize the cases of equality. This resolves, in a strong form, a question of Crane and Russell. |
| title | A note on connectivity in directed graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2409.12137 |