A385629 Number of equivalence classes of connected 4-regular graphs on n unlabeled nodes up to local complementation.

0, 0, 0, 0, 1, 1, 2, 6, 13, 56, 261

Offset

1,7

Comments

Number of equivalences classes of 4-regular graphs on n nodes up to a sequence of local complementation or isomorphism.

a(n) is necessarily less than:

A033301(n) (number of non-isomorphic, not necessarily connected 4-regular graphs);

A006820(n) (number of non-isomophic connected 4-regular graphs);

A090899(n) (number of local equivalence classes of connected graphs); and

A156800(n) (number of equivalence classes for connected graphs up to pivots and isomorphism).

This is relevant in the study of optimal quantum circuit synthesis for graph state preparation.

Links

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

Niels Bohr Institute Center for Hybrid Quantum Networks, graph_table (github)

Tristan Cam, Cyril Gavoille, Yvan Le Borgne, and Simon Martiel, Universal Graph Theory Operations for Graph State Preparation

Example

There are only two 4-regular graphs with 7 nodes and they are not equivalent up to a sequence of local complementation, thus a(7) = 2.

Crossrefs

Cf. A006820, A033301, A090899, A156800.

Sequence in context: A284223 A241784 A211995 * A245010 A057243 A294130

Adjacent sequences: A385626 A385627 A385628 * A385630 A385631 A385632

Keyword

nonn,more

Author

Tristan Cam, Aug 09 2025

Status

approved