A conjeccture concerning strongly connected graphs Original Research Article

Let Cl(n;d be the class of all directed graphsG, without loops and without multiple arcs, such that each graphG hasn vertices andd arcs. A primal subgraph ofG is generated by deleting one vertex and all the arcs going out from this vertex or into it. We conjecture that ifG ε Cl(n;d) where (n(n − 1)/2) + 1 less-than-or-equals, slant d less-than-or-equals, slant n(n − 1), and ifG is strongly connected, then it has a strongly connected primal subgraph. This conjecture is verified forn = 3, 4, and 5 (Theorems 1, 3′ and 5). Two related results hold for all n (Theorems 2 and 4).