There are two distinct notions of connectivity in a directed graph. A directed graph is weakly connected if there is an undirected path between any pair of vertices, and strongly connected if there is a directed path between every pair of vertices. The following tables summarized the number of weakly and strongly connected digraphs on n = 1, 2, ... nodes. The 8 weakly but not strongly connected digraphs on three nodes are illustrated above. connectivity | OEIS | counts weakly connected | A003085 | 1, 2, 13, 199, 9364, ... strongly connected | A035512 | 1, 1, 5, 83, 5048, 1047008, ... weakly but not strongly | A056988 | 0, 1, 8, 116, 4316, 483835, ...

connected graph | directed graph | strongly connected digraph | weakly connected digraph