Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.14393 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911186802442240 |
|---|---|
| author | Jordaan, Richter |
| author_facet | Jordaan, Richter |
| contents | For distinct vertices $u,v$ in a graph $G$, let $κ_G(u,v)$ denote the maximum number of internally disjoint $u$-$v$ paths in $G$. Then, $κ_G(u,v) \leq \min\{ \mbox{deg}_G(u), \mbox{deg}_G(v) \}$. If equality is attained for every pair of vertices in $G$, then $G$ is called ideally connected. In this paper, we characterize the ideally connected graphs in two well-known graph classes: the cographs and the chordal graphs. We show that the ideally connected cographs are precisely the $2K_2$-free cographs, and the ideally connected chordal graphs are precisely the threshold graphs, the graphs that can be constructed from the single-vertex graph by repeatedly adding either an isolated vertex or a dominating vertex. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_14393 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Ideally Connected Cographs and Chordal Graphs Jordaan, Richter Combinatorics For distinct vertices $u,v$ in a graph $G$, let $κ_G(u,v)$ denote the maximum number of internally disjoint $u$-$v$ paths in $G$. Then, $κ_G(u,v) \leq \min\{ \mbox{deg}_G(u), \mbox{deg}_G(v) \}$. If equality is attained for every pair of vertices in $G$, then $G$ is called ideally connected. In this paper, we characterize the ideally connected graphs in two well-known graph classes: the cographs and the chordal graphs. We show that the ideally connected cographs are precisely the $2K_2$-free cographs, and the ideally connected chordal graphs are precisely the threshold graphs, the graphs that can be constructed from the single-vertex graph by repeatedly adding either an isolated vertex or a dominating vertex. |
| title | Ideally Connected Cographs and Chordal Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.14393 |