login
Maximum number of inequivalent orientations of an n-node graph.
1

%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