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,3

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

Links

Table of n, a(n) for n=1..13.

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.

Crossrefs

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

Sequence in context: A367641 A237998 A167939 * A206724 A306187 A009400

Adjacent sequences: A352763 A352764 A352765 * A352767 A352768 A352769

Keyword

nonn,more

Author

Pontus von Brömssen, Apr 02 2022

Status

approved