cp's OEIS Frontend

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

%I A352764 #14 Apr 16 2022 15:04:32
%S A352764 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,
%T A352764 22,23,24,25,26,27,28,29,29,30,31,32,33,34,35,36,37,37,38,39,40,41,42,
%U A352764 43,44,45,46,46,47,48,49,50,51,52,53,54,55,55,56,57,58,59
%N A352764 Smallest number of edges in an asymmetric n-node graph, or -1 if no such graph exists.
%C A352764 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.
%C A352764 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.
%H A352764 Pontus von Brömssen, <a href="/A352764/b352764.txt">Table of n, a(n) for n = 1..10000</a>
%H A352764 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IdentityGraph.html">Identity Graph</a>
%H A352764 Wikipedia, <a href="https://en.wikipedia.org/wiki/Asymmetric_graph">Asymmetric graph</a>
%F A352764 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).
%Y A352764 Cf. A000220, A352765 (number of extremal graphs).
%K A352764 sign
%O A352764 1,6
%A A352764 _Pontus von Brömssen_, Apr 02 2022