- FindStat

edit this statistic or download as text // json

Identifier

St001057: Graphs ⟶ ℤ

Values

([],1) => 1

([],2) => 0

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

([],3) => 1

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

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

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

([],4) => 0

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

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

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

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

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

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

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

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

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

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

([],5) => 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

([],6) => 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>> 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 Grundy value of the game of creating an independent set in a graph.
Two players alternately add a vertex to an initially empty set, which is not adjacent to any of the vertices it already contains.
Alternatively, the game can be described as starting with a graph, the players remove vertices together with their neighbors, until the graph is empty.

References

[1] Tikhomirov, M. Two-player independent set game MathOverflow:282095

Code

@cached_function
def statistic(G, S=frozenset()):
    """Return the Grundy value for the game of deleting vertices until
    the graph has no edges.
    """
    def children():
        for v in G:
            if v not in S and S.isdisjoint(G.neighbors(v)):
                yield S.union([v])

    l = [statistic(G, T) for T in children()]
    i = 0
    while i in l:
        i += 1
    return i

Created

Nov 25, 2017 at 22:14 by Martin Rubey

Updated

Nov 25, 2017 at 22:14 by Martin Rubey