A352764 -id:A352764 - cp's OEIS frontend

A352765 Number of asymmetric n-node graphs with the smallest number (A352764(n)) of edges.

1, 0, 0, 0, 0, 1, 2, 1, 1, 3, 6, 15, 29, 68, 144, 1, 3, 9, 24, 62

Offset: 1

Pontus von Brömssen, Apr 02 2022

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

Pontus von Brömssen, Apr 02 2022

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

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

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.

cp's OEIS Frontend

A352765 Number of asymmetric n-node graphs with the smallest number (A352764(n)) of edges.

Views

Author

Keywords

Crossrefs

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

Views

Author

Keywords

Comments

Crossrefs

Formula