A352766 Maximum number of inequivalent orientations of an n-node graph.

1, 1, 3, 10, 64, 1088, 33792, 4194304, 536870912, 137975824384, 70506183131136, 72127962782105600, 147646010183714340864

Offset: 1

Author

Pontus von Brömssen, Apr 02 2022

Keywords

• nonn
• more

Comments

For n <= 13, the complements of all extremal graphs are acyclic (see A352767). Is this true for all n?

For 10 <= n <= 13, a(n) = 2^(binomial(n,2)-n+2) + 2^(binomial(n-1,2)-n+3).

Crossrefs

Cf. A352764, A352767 (number of extremal graphs).

Formula

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.