Ideally Connected Cographs and Chordal Graphs
arXiv:2509.14393 · doi:10.1016/j.disc.2025.114819
Abstract
For distinct vertices in a graph , let denote the maximum number of internally disjoint - paths in . Then, $κ_G(u,v) \leq \min\{ \mbox{deg}_G(u), \mbox{deg}_G(v) \}$. If equality is attained for every pair of vertices in , then 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 -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!