- FindStat

edit this statistic or download as text // json

Identifier

St001373: Graphs ⟶ ℤ

Values

([],1) => 1

([],2) => 2

([(0,1)],2) => 1

([],3) => 3

([(1,2)],3) => 2

([(0,2),(1,2)],3) => 3

([(0,1),(0,2),(1,2)],3) => 1

([],4) => 4

([(2,3)],4) => 3

([(1,3),(2,3)],4) => 4

([(0,3),(1,3),(2,3)],4) => 3

([(0,3),(1,2)],4) => 2

([(0,3),(1,2),(2,3)],4) => 4

([(1,2),(1,3),(2,3)],4) => 2

([(0,3),(1,2),(1,3),(2,3)],4) => 3

([(0,2),(0,3),(1,2),(1,3)],4) => 4

([(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 3

([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 1

([],5) => 5

([(3,4)],5) => 4

([(2,4),(3,4)],5) => 5

([(1,4),(2,4),(3,4)],5) => 4

([(0,4),(1,4),(2,4),(3,4)],5) => 5

([(1,4),(2,3)],5) => 3

([(1,4),(2,3),(3,4)],5) => 5

([(0,1),(2,4),(3,4)],5) => 4

([(2,3),(2,4),(3,4)],5) => 3

([(0,4),(1,4),(2,3),(3,4)],5) => 5

([(1,4),(2,3),(2,4),(3,4)],5) => 4

([(0,4),(1,4),(2,3),(2,4),(3,4)],5) => 3

([(1,3),(1,4),(2,3),(2,4)],5) => 5

([(0,4),(1,2),(1,3),(2,4),(3,4)],5) => 4

([(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 4

([(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 5

([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 5

([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5) => 5

([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 3

([(0,4),(1,3),(2,3),(2,4)],5) => 4

([(0,1),(2,3),(2,4),(3,4)],5) => 2

([(0,3),(1,2),(1,4),(2,4),(3,4)],5) => 4

([(0,3),(0,4),(1,2),(1,4),(2,4),(3,4)],5) => 3

([(0,3),(0,4),(1,2),(1,4),(2,3)],5) => 5

([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 5

([(0,3),(0,4),(1,2),(1,4),(2,3),(2,4),(3,4)],5) => 5

([(0,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5) => 4

([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 2

([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 3

([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 3

([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4)],5) => 4

([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5) => 5

([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 3

([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 1

([],6) => 6

([(4,5)],6) => 5

([(3,5),(4,5)],6) => 6

([(2,5),(3,5),(4,5)],6) => 5

([(1,5),(2,5),(3,5),(4,5)],6) => 6

([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => 5

([(2,5),(3,4)],6) => 4

([(2,5),(3,4),(4,5)],6) => 6

([(1,2),(3,5),(4,5)],6) => 5

([(3,4),(3,5),(4,5)],6) => 4

([(1,5),(2,5),(3,4),(4,5)],6) => 6

([(0,1),(2,5),(3,5),(4,5)],6) => 4

([(2,5),(3,4),(3,5),(4,5)],6) => 5

([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => 6

([(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 4

([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 5

([(2,4),(2,5),(3,4),(3,5)],6) => 6

([(0,5),(1,5),(2,4),(3,4)],6) => 6

([(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 5

([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => 6

([(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5

([(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 6

([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => 5

([(0,5),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 6

([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6

([(0,5),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 5

([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5

([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 6

([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 4

([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 6

([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4

([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6

([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5

([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 6

([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5

([(0,5),(1,4),(2,3)],6) => 3

([(1,5),(2,4),(3,4),(3,5)],6) => 5

([(0,1),(2,5),(3,4),(4,5)],6) => 5

([(1,2),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => 5

([(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 5

([(0,1),(2,5),(3,4),(3,5),(4,5)],6) => 4

([(0,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 5

([(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 4

([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 3

([(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 6

([(0,5),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 6

([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 6

([(0,5),(1,2),(1,4),(2,3),(3,5),(4,5)],6) => 5

>>> Load all 1200 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

Description

The logarithm of the number of winning configurations of the lights out game on a graph.
In the single player lamps out game, every vertex has two states, on or off. The player can toggle the state of a vertex, in which case all the neighbours of the vertex change state, too. The goal is to reach the configuration with all vertices off.

References

[1] wikipedia:Lights_Out_(game)

Code

def toggle(G, conf, v):
    conf[v] = not conf[v]
    for u in G.neighbor_iterator(v):
        conf[u] = not conf[u]

def statistic(G):
    n = G.num_verts()
    confs = set()
    for s in subsets(G.vertices()):
        new = [True]*n
        for v in s:
            toggle(G, new, v)
        confs.add(tuple(new))
    return log(len(confs),2)

Created

Mar 19, 2019 at 08:06 by Martin Rubey

Updated

Mar 19, 2019 at 08:06 by Martin Rubey