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
Pontus von Brömssen, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Identity Graph
Wikipedia, Asymmetric graph
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).
KEYWORD
sign
AUTHOR
Pontus von Brömssen, Apr 02 2022
STATUS
approved