Timeline for Strongly connected DAG from any connected undirected graph?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 3, 2014 at 13:40 | comment | added | user44191 | Ah; then that property isn't true. Try the 3-star (3 outside vertices all attached to one inside vertex); any orientation will lead to two of the outside vertices having no path between them. | |
| Jul 3, 2014 at 13:34 | comment | added | user44191 | It satisfies the property I described (there is a path to that one vertex); that's the only one I could make sense of given the original post. | |
| Jul 3, 2014 at 13:31 | comment | added | user32851 | Thanks for the help. I think the concept I am looking for is 'acyclic orientation'. Every undirected graph has at least one acyclic orientation. Connectivity of the acyclic orientation is nice but not essential (in the sense that there is a directed path between each node pair, but not that any node can be reached from any other). Thanks! | |
| Jul 3, 2014 at 13:26 | comment | added | Joel David Hamkins | But then it may not be strongly connected. Actually, in any case your construction does not necessarily give a strongly connected digraph, since we might have started with a tree, right? | |
| Jul 3, 2014 at 13:24 | comment | added | user44191 | True; for each distance, you can freely choose any ordering and do the same thing. In other words, you can first choose any ordering on all the vertices, and then use a lexicographical ordering based on distance first and the arbitrary order second. | |
| Jul 3, 2014 at 13:06 | comment | added | Joel David Hamkins | What does your procedure do to specify the direction of edges between nodes that are equidistant from the root? It can matter. For example, if you start with the complete graph (on a graph with at least four vertices), you will have a bunch of arrows coming out of the root, but you haven't done anything to ensure that there will not be a directed cycle amongst the rest of the edges. | |
| Jul 3, 2014 at 10:37 | history | answered | user44191 | CC BY-SA 3.0 |