A334443 Number of unlabeled connected n-vertex graphs for which the lights out puzzle has a unique solution.

1, 0, 1, 2, 9, 33, 290, 3692, 94280, 4454654

Offset

1,4

Comments

The lights out puzzle on a graph has a unique solution if and only if the graph has an odd number of matchings. (See Section 6 in the paper by Eriksson, Eriksson, and Sjöstrand.)

Links

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

H. Eriksson, K. Eriksson, J. Sjöstrand, Note on the lamp lighting problem, Advances in Applied Mathematics 27 (2001), 357-366.

Eric Weisstein's World of Mathematics, Lights Out Puzzle

Example

The connected 4-vertex graphs for which the lights out puzzle has a unique solution are the path and the cycle, so a(4)=2.

Crossrefs

Cf. A076436.

Inverse Euler transform of A334444.

Sequence in context: A150936 A109719 A263685 * A301868 A288958 A212348

Adjacent sequences: A334440 A334441 A334442 * A334444 A334445 A334446

Keyword

nonn,more

Author

Pontus von Brömssen, Apr 30 2020

Status

approved