Questions tagged [acyclic-orientations]

An acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orientation.

Filter by
Sorted by
Tagged with
0
votes
0answers
17 views

Minimum longest acyclic directed path in a graph consisting of two disjoint subgraphs

Consider a simple graph oriented acyclically to obtain a directed graph so as to minimize the longest path. Assume the graph consists of two totally disjoint graphs (empty vertex and edge set ...
5
votes
1answer
143 views

When can we make a digraph acyclic by fliping groups of arcs?

We have a digraph D=(V,A) and its arc set A is partitioned into classes. We can flip the classes, which means changing the direction of all the arcs in the class. Is there any result on when can we ...
3
votes
2answers
569 views

Acyclic orientations of complete graphs in terms of Stirling numbers?

It is well-known that the number of acyclic orientations of $K_n$ is $n!$. Does anybody know of a combinatorial argument for this fact which uses the identity: $$n!=\sum_{k=1}^ns(n,k),$$ where the $...