I need to find the maximum number of topological sorts on Direct Acyclic Graph of Norder. I've checked by running Depth first search algorithm on various Direct Acyclic graphs, and it looks like it is the size of Depth first search algorithm forest that created after running DFS on the graph. Or maybe I completely wrong or miss something. I also need to prove it. Any help will be appreciated. Thank you.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This should be a comment, but I don't have the reputation. Unless you specify more information about your graph, there is likely to be no good answer. To phrase your question in a more Mathoverflowese manner, you are looking for the number of linear extensions of a poset. This is known to be difficult in general, but formulas are known for some special cases. 

