- FindStat

edit this statistic or download as text // json

Identifier

St001395: Graphs ⟶ ℤ

Values

([],1) => 0

([],2) => 0

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

([],3) => 0

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

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

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

([],4) => 0

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

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

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

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

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

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

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

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

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

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

([],5) => 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

([(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) => 1

([(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) => 0

([(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) => 0

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

([(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) => 3

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

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

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

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

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

([],6) => 0

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

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

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

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

([(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) => 0

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

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

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

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

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

([(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) => 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

([(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) => 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

([(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) => 0

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

>>> 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 number of strictly unfriendly partitions of a graph.
A strictly unfriendly partitions of a graph is a two-colouring of its vertices such that every vertex has more neighbours of the other colour than of the same colour.
This statistic returns the number of strictly unfriendly partitions, up to switching the colours. For example, the complete graph on four vertices has three strictly unfriendly partitions: the three set partitions of the vertices into two blocks of size two.

References

[1] Spadaro, S. Strict unfriendly partitions MathOverflow:332200

Code

def unfriendly(G, s):
    for v in G.vertices():
        if v in s:
            count = sum(1 for u in G[v] if u in s)
        else:
            count = sum(1 for u in G[v] if u not in s)            
        if count >= len(G[v])-count:
            return False
    return True

def statistic(G):
    n = G.num_verts()
    if not n:
        return 1
    H = G.relabel(inplace=False)
    return sum(1 for s in subsets(range(1, n)) if unfriendly(H, [0] + s))

Created

May 22, 2019 at 22:46 by Martin Rubey

Updated

Dec 26, 2020 at 02:33 by Martin Rubey