Mixing
How many different graphs of order $n$ are there?
up vote
2
down vote
favorite
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 24*n. For DAGs, it's about 23*n.]
[Note: I tagged this under "descriptive complexity" because it's not really a simulation. Let me know if this is wrong.]
graph-theory combinatorial-geometry descriptive-complexity
asked yesterday
theDoctor
215213
add a comment |
up vote
2
down vote
favorite
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 24*n. For DAGs, it's about 23*n.]
[Note: I tagged this under "descriptive complexity" because it's not really a simulation. Let me know if this is wrong.]
graph-theory combinatorial-geometry descriptive-complexity
asked yesterday
theDoctor
215213
Labeled or unlabeled? (For instance, are there $frac12 n!$ path graphs on $n$ vertices, or only $1$?)
– Misha Lavrov
yesterday
In my understanding of "labeled" graphs, there would be an infinite number, so it's inapplicable.
– theDoctor
yesterday
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?
– Misha Lavrov
yesterday
@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.
– theDoctor
yesterday
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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 24*n. For DAGs, it's about 23*n.]
[Note: I tagged this under "descriptive complexity" because it's not really a simulation. Let me know if this is wrong.]
graph-theory combinatorial-geometry descriptive-complexity
asked yesterday
theDoctor
215213
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 24*n. For DAGs, it's about 23*n.]
[Note: I tagged this under "descriptive complexity" because it's not really a simulation. Let me know if this is wrong.]
graph-theory combinatorial-geometry descriptive-complexity
graph-theory combinatorial-geometry descriptive-complexity
asked yesterday
theDoctor
215213
asked yesterday
theDoctor
215213
edited yesterday
asked yesterday
theDoctor
215213
asked yesterday
theDoctor
215213
asked yesterday
theDoctor
215213
215213
Labeled or unlabeled? (For instance, are there $frac12 n!$ path graphs on $n$ vertices, or only $1$?)
– Misha Lavrov
yesterday
In my understanding of "labeled" graphs, there would be an infinite number, so it's inapplicable.
– theDoctor
yesterday
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?
– Misha Lavrov
yesterday
@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.
– theDoctor
yesterday
add a comment |
Labeled or unlabeled? (For instance, are there $frac12 n!$ path graphs on $n$ vertices, or only $1$?)
– Misha Lavrov
yesterday
In my understanding of "labeled" graphs, there would be an infinite number, so it's inapplicable.
– theDoctor
yesterday
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?
– Misha Lavrov
yesterday
@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.
– theDoctor
yesterday
Labeled or unlabeled? (For instance, are there $frac12 n!$ path graphs on $n$ vertices, or only $1$?)
– Misha Lavrov
yesterday
Labeled or unlabeled? (For instance, are there $frac12 n!$ path graphs on $n$ vertices, or only $1$?)
– Misha Lavrov
yesterday
In my understanding of "labeled" graphs, there would be an infinite number, so it's inapplicable.
– theDoctor
yesterday
In my understanding of "labeled" graphs, there would be an infinite number, so it's inapplicable.
– theDoctor
yesterday
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?
– Misha Lavrov
yesterday
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?
– Misha Lavrov
yesterday
@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.
– theDoctor
yesterday
@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.
– theDoctor
yesterday
add a comment |
1 Answer
1
active
oldest
votes
up vote
5
down vote
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!$.
answered yesterday
Travis
58.7k765142
1
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).
– Marko Riedel
yesterday
That is amazing. Thanks for the answer! I will evaluate further.
– theDoctor
yesterday
You're welcome. I've added a reference to A286743.
– Travis
yesterday
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
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!$.
answered yesterday
Travis
58.7k765142
1
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).
– Marko Riedel
yesterday
That is amazing. Thanks for the answer! I will evaluate further.
– theDoctor
yesterday
You're welcome. I've added a reference to A286743.
– Travis
yesterday
add a comment |
up vote
5
down vote
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!$.
answered yesterday
Travis
58.7k765142
1
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).
– Marko Riedel
yesterday
That is amazing. Thanks for the answer! I will evaluate further.
– theDoctor
yesterday
You're welcome. I've added a reference to A286743.
– Travis
yesterday
add a comment |
up vote
5
down vote
up vote
5
down vote
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!$.
answered yesterday
Travis
58.7k765142
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!$.
answered yesterday
Travis
58.7k765142
edited yesterday
answered yesterday
Travis
58.7k765142
answered yesterday
Travis
58.7k765142
answered yesterday
Travis
58.7k765142
58.7k765142
1
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).
– Marko Riedel
yesterday
That is amazing. Thanks for the answer! I will evaluate further.
– theDoctor
yesterday
You're welcome. I've added a reference to A286743.
– Travis
yesterday
add a comment |
1
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).
– Marko Riedel
yesterday
That is amazing. Thanks for the answer! I will evaluate further.
– theDoctor
yesterday
You're welcome. I've added a reference to A286743.
– Travis
yesterday
1
1
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).
– Marko Riedel
yesterday
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).
– Marko Riedel
yesterday
That is amazing. Thanks for the answer! I will evaluate further.
– theDoctor
yesterday
That is amazing. Thanks for the answer! I will evaluate further.
– theDoctor
yesterday
You're welcome. I've added a reference to A286743.
– Travis
yesterday
You're welcome. I've added a reference to A286743.
– Travis
yesterday
add a comment |
draft saved
draft discarded
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3005230%2fhow-many-different-graphs-of-order-n-are-there%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Labeled or unlabeled? (For instance, are there $frac12 n!$ path graphs on $n$ vertices, or only $1$?)
– Misha Lavrov
yesterday
In my understanding of "labeled" graphs, there would be an infinite number, so it's inapplicable.
– theDoctor
yesterday
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?
– Misha Lavrov
yesterday
@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.
– theDoctor
yesterday