- FindStat

edit this statistic or download as text // json

Identifier

St001362: Graphs ⟶ ℤ

Values

([],1) => 0

([],2) => 0

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

([],3) => 0

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

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

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

([],4) => 0

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

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

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

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

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

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

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

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

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

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

([],5) => 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

([],6) => 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

>>> 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 normalized Knill dimension of a graph.
The Knill dimension [1], [2] is a rational number associated with a graph as follows: for the empty graph $\dim(G) = -1$. For a graph with non-empty vertex set $V$, it is $\dim(G) = 1 + \frac{1}{|V|}\sum_{v\in V}\dim(N_v)$, where
$N_v$ is the subgraph of $G$ induced by the set of neighbours of $v$.
Conjecturally, the least common multiple of the denominators of all graphs is the order of the alternating group oeis:A001710. Thus, the normalized Knill dimension is the Knill dimension multiplied with the number.

References

[1] Knill, O. A discrete Gauss-Bonnet type theorem MathSciNet:2888693 arXiv:1009.2292
[2] Knill, O. On the Dimension and Euler characteristic of random graphs arXiv:1112.5749
[3] Betre, K., Salinger, E. The Knill Graph Dimension from The Minimum Clique Cover arXiv:1903.02523

Code

def statistic(G):
    return dim_knill(G)*numerator(factorial(G.num_verts())/2)

def dim_knill(G):
    return dim_knill_aux1(G.copy(immutable=True))

@cached_function
def dim_knill_aux1(G):
    if not G.num_verts():
        return -1
    return sum(dim_knill_aux2(G, v) for v in G.vertices())/G.num_verts()

@cached_function
def dim_knill_aux2(G, v):
    return 1 + dim_knill_aux1(G.subgraph(G.neighbors(v)))

Created

Mar 07, 2019 at 09:36 by Martin Rubey

Updated

Mar 10, 2019 at 16:32 by Martin Rubey