Given an asymmetric relation $A\subseteq V^2$ a digraph $D=(V,A)$ is minimally strong iff $D$ is strongly connected and for all arcs $\alpha\in A$ the digraph $D−\alpha=(V,A\setminus\{\alpha\})$ is not strongly connected.

Now by Robbins' theorem a graph has a strong orientation iff said graph has an ear decomposition iff said graph is $2$-edge connected. Thus clearly every graph with a minimally strong orientation will be $2$-edge connected, however it is easy to see that many such graphs do not have any minimally strong orientations. For instance wheel graphs are $2$-edge connected, though no wheel graph has a minimally strong orientation. I can prove when a graph $G$ has a minimally strong orientation then we have the inequality $|V(G)|\leq |E(G)|\leq 2|V(G)|-2$ as well as $\delta(G)=2$ and $\chi(G)\leq 3$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.