Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #7 Apr 16 2022 05:48:34
%S 1,1,3,10,64,1088,33792,4194304,536870912,137975824384,70506183131136,
%T 72127962782105600,147646010183714340864
%N Maximum number of inequivalent orientations of an n-node graph.
%C For n <= 13, the complements of all extremal graphs are acyclic (see A352767). Is this true for all n?
%C For 10 <= n <= 13, a(n) = 2^(binomial(n,2)-n+2) + 2^(binomial(n-1,2)-n+3).
%F For n >= 6, a(n) >= 2^(binomial(n,2)-A352764(n)), because if G is the complement of an asymmetric n-node graph with A352764(n) edges, all its 2^(binomial(n,2)-A352764(n)) orientations are pairwise inequivalent. Equality holds for n = 8 and n = 9, but for all other n between 6 and 13 we can do better by trading the asymmetry for more edges.
%Y Cf. A352764, A352767 (number of extremal graphs).
%K nonn,more
%O 1,3
%A _Pontus von Brömssen_, Apr 02 2022