3
$\begingroup$

I'm interested in all four combinations: directed and undirected, cyclic and acyclic.

I'm having trouble calculating how big the complexity gets as you add more nodes to a graph. Clearly, the number of possible graphs goes up with adding directability, and wildly (adding Ω(2n) complexity, roughly).

My best guess on a DAG is close to Ω(n!).

[Edit: "multigraphs", obviously, aren't part of the question.]

[Edit2: Looks like for DCGs, it is about 23n. For DAGs, it's about 22n.]

[Note: I tagged this under "descriptive complexity" because it's not really a simulation. Let me know if this is wrong.]

$\endgroup$
  • $\begingroup$ Labeled or unlabeled? (For instance, are there $\frac12 n!$ path graphs on $n$ vertices, or only $1$?) $\endgroup$ – Misha Lavrov Nov 19 '18 at 19:06
  • $\begingroup$ In my understanding of "labeled" graphs, there would be an infinite number, so it's inapplicable. $\endgroup$ – theDoctor Nov 19 '18 at 19:07
  • $\begingroup$ Labeled graphs in the sense that we name the vertices $v_1, v_2, \dots, v_n$ (or if you prefer just $1, 2, \dots, n$) and go from there. This is the standard thing to do when, for example, we count labeled trees. Another way to phrase my question: do you want to count isomorphic graphs multiple times or not? $\endgroup$ – Misha Lavrov Nov 19 '18 at 19:10
  • $\begingroup$ @MishaLavrov: No isomorphic graphs are not counted multiple times. Labeling a graph was not considered proper graph theory in my education, any more than putting the mileage on the edges between cities. $\endgroup$ – theDoctor Nov 19 '18 at 19:17
  • $\begingroup$ @MishaLavrov: I think we/I have to reconsider your question wrt labeled or not. A 2-vertex DAG from v1 to v2 is counted separately than a graph of v2 to v1, even though they are "isomorophic" without regarding labels. The reason is that a vertex is generally anchored to some meaning outside the graph even though a graph's definition doesn't care. $\endgroup$ – theDoctor May 16 at 18:10
7
$\begingroup$

In general these counts do not have nice closed formulas, but some satisfy nice recurrence relations.

Graphs

  • Graphs on $n$ nodes is OEIS A000088: $$1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, \ldots .$$ Flajolet & Sedgwick's Analytic Combinatorics, $\S~$II.5 gives that this sequence is asymptotic to $2^{\frac{1}{2} n (n - 1)}/n!$. (They cite Harary & Palmer's text Graphical Enumeration for this fact, but I haven't checked it myself. Probably that reference gives some of the below data, too.)
  • Acyclic graphs on $n$ nodes (forests) is A005195: $$1, 1, 2, 3, 6, 10, 20, 37, 76, 153, \ldots .$$ This is asymptotic to $c n^{-5/2} d^n$ for some $c > 0$ and $d > 1$.
  • Cyclic graphs on $n$ nodes is A286743: $$0, 0, 1, 5, 24, 136, 1007, 12270, 274515, 12004839, \ldots .$$ By definition this is just [A000088] - [A005195]. The latter has much smaller growth than the former, so this also asymptotic to $2^{\frac{1}{2} n (n - 1)}/n!$.

Directed graphs

  • Directed graphs on $n$ nodes is OEIS A000273: $$1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, \ldots .$$ This is asymptotic to $2^{n (n - 1)}/n!$
  • Directed acyclic graphs on $n$ nodes is OEIS A003087: $$1, 1, 2, 6, 31, 302, 5984, 243668, 20286025, 3424938010, \ldots .$$ OEIS doesn't give asymptotics for this sequence, but we can deduce from asymptotics for the case of labeled directed acyclic graphs that this sequence is asymptotic to some function in between $A p^{-n} 2^{\frac{1}{2} n (n - 1)}$ and $A p^{-n} 2^{\frac{1}{2} n (n - 1)} n!$ for some $A > 0$ and $p > 1$. In any case before this is much slower growth than the count for directed graphs, so graphs on $n$ nodes that have at least one cycle is also asymptotic to $2^{n (n - 1)} / n!$.
$\endgroup$
  • 1
    $\begingroup$ A compact Maple routine for OEIS A000088 may be found at the following MSE link (scroll to end of post, is not limited to question from title of link). $\endgroup$ – Marko Riedel Nov 19 '18 at 20:01
  • $\begingroup$ That is amazing. Thanks for the answer! I will evaluate further. $\endgroup$ – theDoctor Nov 19 '18 at 21:27
  • $\begingroup$ You're welcome. I've added a reference to A286743. $\endgroup$ – Travis Nov 19 '18 at 22:24
  • $\begingroup$ @Travis: My analysis says a DAG should be asymptotic to 2<sup>3n</sup> and a DCG to 2<sup>4n</sup>. I tested my asymptotic on DCG and it was more accurate, but there's not much data. $\endgroup$ – theDoctor Nov 28 '18 at 21:30
  • $\begingroup$ I haven't redone the calculation myself, but the cited rate for D.A.G. comes from the linked OEIS entry, which cites: M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports 17 (1955), 14-22. A hand-annotated pdf copy can be found at oeis.org/A000088/a000088.pdf In that article the relevant sequence is denoted $\textrm{ref}_n$. $\endgroup$ – Travis Nov 29 '18 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.