2
$\begingroup$

I have the following question. It seems likely to be true - can anyone provide a standard reference?

Given: A connected, undirected graph.

Question 1: Can we assume a single direction for each edge such that the resulting directed graph is acyclic and strongly connected (path exists in one direction)?

Question 2: Suppose that if $i< j$ and there is an edge between $i$ and $j$ in the undirected graph, the edge in the directed graph is pointing from $i$ to $j$. Is there always a node numbering such that the resulting graph is strongly connected and acyclic? (e.g. would numbering down the branches of a spanning tree in the undirected graph work?)

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ What you mean by "strongly connected" doesn't seem to be the standard usage; an a cyclic graph can only be strongly connected if it has one vertex. I've answered below assuming I understood what you mean by "strongly connected" correctly. You also seem to have dropped your second question. $\endgroup$
    – user44191
    Commented Jul 3, 2014 at 10:28
  • 2
    $\begingroup$ Strongly connected (for a directed graph) usually means that between any two vertices there exist directed paths from one to the other; frequently, this is called diconnected. A possible counter-example (if I've understood the question correctly) is the edge and vertex set of the unit cube. $\endgroup$
    – David Handelman
    Commented Jul 3, 2014 at 11:19
  • $\begingroup$ As for question 2, a directed graph is acyclic if and only if there is a numbering of its vertices satisfying the condition in the first sentence. This has nothing to do with connectedness. $\endgroup$
    – Emil Jeřábek
    Commented Jul 3, 2014 at 12:16
  • $\begingroup$ @Emil, if "number" here means natural number or integer, then your equivalence, although true for finite graphs, is not true for all infinite graphs, since some infinite acyclic digraphs cannot be $\mathbb{Z}$-graded (such as the digraph of the usual $\leq$ relation on $\mathbb{Q}$). Meanwhile, a countable digraph is acyclic if and only if it can be $\mathbb{Q}$-graded, and in general, any digraph is acyclic just in case it is graded by some linear order. $\endgroup$
    – Joel David Hamkins
    Commented Jul 3, 2014 at 15:29
  • $\begingroup$ @Joel: Given the context, I am assuming that graphs are finite by definition, as usual in discrete mathematics. I would be extremely surprised if that’s not what the OP intended. Anyway, I never said anything about integers, so please be that kind and do not put words in my mouth, or at least if you do, choose an interpretation that spares lives of innocent straw men. $\endgroup$
    – Emil Jeřábek
    Commented Jul 3, 2014 at 16:05

2 Answers 2

Reset to default
4
$\begingroup$

The answer to both questions is negative, if one wants to have an acyclic digraph that is strongly connected, in the sense that any two nodes have a directed path between them in one direction or the other.

A counterexample is provided by any tree having at least three leaves. It must be that two of the leaves are sources, or two are sinks, and in either case, there is no directed path between those two leaves.

If you drop the connectivity requirement, as you have suggested, then it is easy: place any linear order on the vertices of the original graph, and simply orient the edges to conform with that order. This is called a grading. Since you asked for a reference, graded digraphs are used in Every model of set theory embeds into its own constructible universe, where I develop a little of the theory in section 2, but I assume this is a standard topic in graph theory and there must be other references.

Improve this answer
$\endgroup$
3
$\begingroup$

You can construct such a directed graph relatively easily (if I've understood your question correctly); choose one vertex, and "hang" the rest of the graph from that vertex (i.e. create a "distance function" that specifies how far a vertex is from your original vertex). Then give each edge a "downwards" direction (i.e. the direction of increasing distance); then every vertex is reachable from that original vertex.

If I've misunderstood your question, then test your question on the two connected 3-vertex graphs; that should give an answer.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Joel David Hamkins
    Commented Jul 3, 2014 at 13:06
  • $\begingroup$ 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. $\endgroup$
    – user44191
    Commented Jul 3, 2014 at 13:24
  • $\begingroup$ 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? $\endgroup$
    – Joel David Hamkins
    Commented Jul 3, 2014 at 13:26
  • $\begingroup$ 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! $\endgroup$
    – user32851
    Commented Jul 3, 2014 at 13:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – user44191
    Commented Jul 3, 2014 at 13:34

You must log in to answer this question.