A352764 Smallest number of edges in an asymmetric n-node graph, or -1 if no such graph exists.

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

Offset: 1

Author

Pontus von Brömssen, Apr 02 2022

Keywords

• sign

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

Crossrefs

Cf. A000220, A352765 (number of extremal graphs).

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).