In a directed graph $G(V, E)$; how can I define in symbols the set of subgraphs $G'=(V',E')$ of $G$ such that $G'$ has a root vertex, i.e., a vertex that sends a directed path in $G'$ to every $v\in V'$.

So far, I have the following. I need to say that

$$\forall v \in V'\, \exists \text{ a directed path $P$ from $r$ to $v$, with all edges in $E'$}\,.$$

This directed path P can be thought as a sequence $(e_1, ..., e_n)$ , where each $e_i$ $\in E'$ and root r is P source. But now I don't know how to continue.

  • $\begingroup$ By "algebraic characterization", I mean just expressing the required in terms of Algebra instead of text description. No you didn't change the meaning, but I'm afraid it's a little less clear in this form. The only challenge in my question now is: formalizing the paths (chain of edges in the same direction) connecting the root vertex and each of the vertices of G′. $\endgroup$ – Median Hilal Nov 26 '14 at 19:25
  • $\begingroup$ Feel free to undo the edit if you don't think it was helpful. $\endgroup$ – David Richerby Nov 26 '14 at 19:27
  • 3
    $\begingroup$ My advice would be don't try to write this in symbols. Writing it in symbols is horrible, complicated and very easy to get wrong. When you eventually get it right, the person reading it will have to think for fifteen minutes and will then, I guarantee, say something that's equivalent to "Oh. He means that the subgraph has a vertex that sends a directed path to every other vertex. Why didn't he just say that?" only using more swear-words. $\endgroup$ – David Richerby Nov 26 '14 at 19:28
  • $\begingroup$ Yes, you are right, I will keep it in this form. I used symbols because I need this in symbols, so I thought I'm helping in shaping the answer just. However, this is clearer and the reader will understand it easily. $\endgroup$ – Median Hilal Nov 26 '14 at 19:30
  • $\begingroup$ I restored your partial answer to the question because it's important to show that you've attempted to solve the problem yourself before asking here. I shouldn't have deleted that! $\endgroup$ – David Richerby Nov 26 '14 at 21:03

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.