|
| |
|
|
A352764
|
|
Smallest number of edges in an asymmetric n-node graph, or -1 if no such graph exists.
|
|
3
|
|
|
|
0, -1, -1, -1, -1, 6, 6, 6, 7, 8, 9, 10, 11, 12, 13, 13, 14, 15, 16, 17, 18, 19, 20, 21, 21, 22, 23, 24, 25, 26, 27, 28, 29, 29, 30, 31, 32, 33, 34, 35, 36, 37, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 55, 56, 57, 58, 59
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,6
|
|
|
COMMENTS
|
For n >= 7, there exists an asymmetric forest with n nodes and a(n) edges. Proof: Let G be a graph with n nodes and a(n) edges, and assume that it has a cyclic component C, which must have at least 6 nodes. (The only asymmetric graph with less than 6 nodes is the 1-node graph.) There exist asymmetric trees of all orders >= 7, so a(n) < n and at least one component of G must be a tree. Let T be such a component with the largest number of nodes. If we replace C and T with an asymmetric tree, keeping the total number of nodes fixed, the resulting graph is still asymmetric (the new tree is larger than all other acyclic components in G), has a(n) edges (by definition, it cannot have less than a(n) edges, so C can only have one cycle), and one cyclic component less than G. This process can be repeated until an acyclic graph with a(n) edges and n nodes is obtained.
For some n, there also exist cyclic asymmetric graphs with a(n) edges, e.g., when n = 6, 7, 14, or 15. This is likely to occur when n is just below Sum_{k=1..m} t(k) for some m, with t(k) as defined in the Formula section.
|
|
|
LINKS
|
|
|
|
FORMULA
|
For n >= 7, a(n) = n-m, where m is the largest positive integer with Sum_{k=1..m} t(k) <= n and t(k) is the order of the k-th largest asymmetric tree (so the sequence (t(k)) is nondecreasing and has A000220(j) occurrences of j).
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
sign
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
