Values
=>
Cc0020;cc-rep
([],1)=>0
([],2)=>1
([(0,1)],2)=>1
([],3)=>1
([(0,2),(1,2)],3)=>2
([(0,1),(0,2),(1,2)],3)=>2
([],4)=>1
([(1,3),(2,3)],4)=>1
([(0,3),(1,3),(2,3)],4)=>2
([(0,3),(1,2),(2,3)],4)=>1
([(1,2),(1,3),(2,3)],4)=>2
([(0,3),(1,2),(1,3),(2,3)],4)=>2
([(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)=>3
([],5)=>1
([(2,4),(3,4)],5)=>1
([(0,4),(1,4),(2,4),(3,4)],5)=>2
([(1,4),(2,3),(3,4)],5)=>1
([(0,1),(2,4),(3,4)],5)=>1
([(2,3),(2,4),(3,4)],5)=>2
([(1,4),(2,3),(2,4),(3,4)],5)=>2
([(0,4),(1,4),(2,3),(2,4),(3,4)],5)=>2
([(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>2
([(0,4),(1,3),(2,3),(2,4),(3,4)],5)=>2
([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>2
([(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)=>1
([(0,1),(2,3),(2,4),(3,4)],5)=>2
([(0,3),(1,2),(1,4),(2,4),(3,4)],5)=>2
([(0,3),(0,4),(1,2),(1,4),(2,4),(3,4)],5)=>2
([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5)=>2
([(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)=>2
([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>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),(3,4)],5)=>3
([(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)=>4
([],6)=>1
([(3,5),(4,5)],6)=>1
([(0,5),(1,5),(2,5),(3,5),(4,5)],6)=>2
([(2,5),(3,4),(4,5)],6)=>1
([(1,2),(3,5),(4,5)],6)=>1
([(3,4),(3,5),(4,5)],6)=>2
([(2,5),(3,4),(3,5),(4,5)],6)=>2
([(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,5),(2,4),(3,4)],6)=>1
([(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>2
([(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
([(0,5),(1,4),(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),(4,5)],6)=>3
([(1,5),(2,4),(3,4),(3,5)],6)=>1
([(0,1),(2,5),(3,4),(4,5)],6)=>1
([(1,2),(3,4),(3,5),(4,5)],6)=>2
([(1,4),(2,3),(2,5),(3,5),(4,5)],6)=>2
([(0,1),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>2
([(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>2
([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>2
([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>2
([(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,4),(2,3),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,4),(2,3),(2,4),(3,5)],6)=>1
([(0,5),(1,5),(2,3),(2,4),(3,4)],6)=>2
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5)],6)=>2
([(0,4),(1,2),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,1),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(1,4),(2,3),(2,5),(3,5),(4,5)],6)=>2
([(0,3),(0,4),(1,2),(1,5),(2,5),(3,5),(4,5)],6)=>2
([(0,3),(1,4),(1,5),(2,4),(2,5),(3,5),(4,5)],6)=>2
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,1),(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>2
([(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>2
([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,2),(1,4),(2,3),(3,4),(3,5),(4,5)],6)=>2
([(0,1),(0,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(0,5),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(0,1),(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>2
([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,4),(0,5),(1,2),(1,3),(2,3),(4,5)],6)=>2
([(0,2),(1,4),(1,5),(2,3),(3,4),(3,5),(4,5)],6)=>2
([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(4,5)],6)=>2
([(0,1),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>2
([(0,1),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,1),(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(2,3),(2,5),(3,4),(4,5)],6)=>2
([(0,3),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,3),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,1),(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,2),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,1),(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>5
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
Description
The Colin de Verdière graph invariant.
References
[1] wikipedia:Colin_de_Verdière_graph_invariant
[2] van der Holst, H., Lovász, L., Schrijver, A. The Colin de Verdière graph parameter MathSciNet:1673503
[3] Goldberg, F., Berman, A. On the Colin de Verdière number of graphs MathSciNet:2775745
[4] Tait, M. The Colin de Verdi\`ere parameter, excluded minors, and the spectral radius arXiv:1703.09732
[2] van der Holst, H., Lovász, L., Schrijver, A. The Colin de Verdière graph parameter MathSciNet:1673503
[3] Goldberg, F., Berman, A. On the Colin de Verdière number of graphs MathSciNet:2775745
[4] Tait, M. The Colin de Verdi\`ere parameter, excluded minors, and the spectral radius arXiv:1703.09732
Code
def statistic(G):
mu = lower_and_upper_bounds(G.copy(immutable=True))
if mu[0] == mu[1]:
return mu[0]
@cached_function
def lower_and_upper_bounds(G, assume_Colin_conjecture=False):
if G.is_clique():
return (G.num_verts()-1, G.num_verts()-1)
if G.num_verts() >= 2 and G.num_edges() == 0:
# Goldberg, Berman (2011), prop. 6.7
return (1,1)
w = G.clique_number()
# Goldberg, Berman (2011), cor. 2.4
lower = w-1
# Goldberg, Berman (2011), thm. 2.3 and mu(K_n)=n-1
upper = G.num_verts()-1
degrees = G.degree()
if max(degrees) == 2 and G.is_forest():
# Goldberg, Berman (2011), thm 2.6 (1)
upper = 1
elif G.is_circular_planar():
# Goldberg, Berman (2011), thm 2.6 (2)
upper = 2
elif G.is_planar():
# Goldberg, Berman (2011), thm 2.6 (3)
upper = 3
# Goldberg, Berman (2011), thm 5.4
upper = min(upper, G.treewidth()+1)
if G.is_chordal():
# Goldberg, Berman (2011), thm 4.1
upper = min(upper, w)
if assume_Colin_conjecture:
# Goldberg, Berman (2011), conj 2.7
lower = max(lower, G.chromatic_number()-1)
# Holst, Lovasz, and Schrijver (1999)
# see Tait (2017), thm 7
for v, d in G.degree(labels=True).iteritems():
H = G.copy(immutable=False)
H.delete_vertex(v)
H = H.copy(immutable=True)
mu_H = lower_and_upper_bounds(H, assume_Colin_conjecture=assume_Colin_conjecture)
# equality is achieved if G has at least one edge (which we know at this point) and
# v is connected to all other vertices
if mu_H[0] == mu_H[1] and d == G.num_verts()-1:
return (mu_H[0]+1, mu_H[0]+1)
upper = min(upper, mu_H[1] + 1)
if lower == upper:
return (lower, upper)
return (lower, upper)
Created
Mar 30, 2017 at 09:11 by Martin Rubey
Updated
Mar 31, 2017 at 11:31 by Martin Rubey
searching the database
Sorry, this statistic was not found in the database
or
add this statistic to the database – it's very simple and we need your support!