# A property and operation on the strong digraph

The strong digraph is a directed graph in which every pair of vertices is going to have a directed path from both ways. Let $G$ be a connected graph with cut-vertices. How to show that an orientation $D$ of $G$ is strong if and only if the subdigraph of $D$ induced by the vertices of each block of $G$ is strong?

The line digraph of a strong digraph is a strong digraph for known families of digraphs, is it true in general?

• What is block of digraph? Apr 11 '17 at 9:30

Suppose there is a graph $G$ and its strong orientation $D$ such that there is a block $B$ of graph $G$ such that corresponding subdigraph $B_D = D(V(B))$ is not strong.

Let there be vertices $u$ and $v$ such that there is no directed $(u, v)$-path inside $B_D$, but there is a directed $(u, v)$-path in $D$. This means that $(u, v)$-path goes through some cut-vertex $w$ outside of $B_D$ and then returns in to $B_D$. But when it returns to $B_D$ it goes again through $w$ otherwise $w$ is not a cut-vertex ans/or $B$ is not a block. Then we can remove part of path between the first occurrence of $w$ and the last orccurrence of $w$. Doing that for each cur-vertex we get a path inside $B_D$. This contrary shows that if $D$ is strong than $B_D$ is strong.

Let orientation $B_D$ of each block $B$ be strong. Now we will show that $D$ is strong. Really let vertices $u$ and $v$ be in different blocks and $(u, v)$-path in $G$ contain cut-vertices $w_1, w_2, \ldots, w_k$ in this order. Since each block is strong then there are directed paths between $u$ and $w_1$, $w_1$ and $w_2$, \ldots, $w_{k - 1}$ and $w_k$, $w_k$ and $u$ in digraph $D$. Concatenating all these paths we get a directed $(u, v)$-path for all $u$ and $v$ from different block. And there is an $(u, v)$-path for all $u$ and $v$ from the same block since each block is strong. So $D$ is strong if and only if each subdigraph of $D$ induced by the vertices of block of $G$ is strong.

For the second question the answer is yes, line digraph $L(G)$ of a strong digraph $G$ is also strong. Let $(u, v)$ and $(x, y)$ be arbitrary directed edges of $G$ (and therefore vertices of $L(G)$). There is a directed $(v, x)$-path in $G$, let it be $v = w_0, w_1, \ldots, w_k = x$. Then there is a directed path $$(u, v), (w_0, w_1), (w_1, w_2), \ldots, (w_{k - 1}, w_k), (x, y)$$ in $L(G)$. Then $L(G)$ is strong since we've chosen arbitrary ordered pair of vertices of $L(G)$.

• Thanks .I've edited the second question .
– hali
Apr 11 '17 at 11:12
• I've added answer for the first question. Apr 11 '17 at 13:37
• The fact that $B_D$ is strong , does it imply that there's a path from $u$ Or $v$ that goes through the cut-vertices ?
– hali
Apr 14 '17 at 11:25
• I mean it only implies that there's a path between each pair of vertices inside $B_D$.
– hali
Apr 14 '17 at 11:27
• Note that to find cut-vertices $w_1, \ldots w_k$ I use undirected $(u, v)$-path in graph $G$. If $u$ and $v$ are in different blocks then this path goes through at least one cut-vertex. Apr 14 '17 at 11:41