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?

  • $\begingroup$ What is block of digraph? $\endgroup$
    – Smylic
    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)$.

  • $\begingroup$ Thanks .I've edited the second question . $\endgroup$
    – hali
    Apr 11 '17 at 11:12
  • $\begingroup$ I've added answer for the first question. $\endgroup$
    – Smylic
    Apr 11 '17 at 13:37
  • $\begingroup$ 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 ? $\endgroup$
    – hali
    Apr 14 '17 at 11:25
  • $\begingroup$ I mean it only implies that there's a path between each pair of vertices inside $B_D$. $\endgroup$
    – hali
    Apr 14 '17 at 11:27
  • $\begingroup$ 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. $\endgroup$
    – Smylic
    Apr 14 '17 at 11:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.