
arXiv: 2509.14393
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.
16 pages, 4 figures. Comments are welcome!
Combinatorics, FOS: Mathematics, Combinatorics (math.CO)
Combinatorics, FOS: Mathematics, Combinatorics (math.CO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
