Semiconnected

Semiconnected is a property of directed graphs. A directed graph G is semiconnected if for every pair of vertices u and v, there exists a directed path from u to v or from v to u (or both). Intuitively, for any two vertices one can reach the other in at least one direction.

A useful characterization uses the condensation of G. Let the strongly connected components of G be contracted to a single vertex to form the condensation DAG D(G). Then G is semiconnected if and only if D(G) is a directed path (a chain). Equivalently, the SCCs can be arranged in a linear order C1, C2, ..., Ck such that there are edges from Ci to Ci+1 for all i, which guarantees that for any i < j there is a path from any vertex in Ci to any vertex in Cj.

Relation to other notions: Every strongly connected digraph is semiconnected, but the converse is not true. For example, a transitive tournament—where vertices can be totally ordered so that all edges go from earlier to later— is semiconnected (for any pair, the earlier vertex can reach the later one) but not strongly connected.

Variants and recognition: In standard graph theory, semiconnectivity is defined for directed graphs (often considered without multiple edges or loops). To decide semiconnectivity algorithmically, compute the strongly connected components (via Tarjan’s or Kosaraju’s algorithm) to form the condensation DAG, then check whether this DAG is a simple directed path. This can be done in linear time relative to the size of the graph.