Values
=>
Cc0020;cc-rep
([],1)=>1
([],2)=>1
([(0,1)],2)=>1
([],3)=>1
([(1,2)],3)=>2
([(0,2),(1,2)],3)=>2
([(0,1),(0,2),(1,2)],3)=>1
([],4)=>1
([(2,3)],4)=>2
([(1,3),(2,3)],4)=>2
([(0,3),(1,3),(2,3)],4)=>2
([(0,3),(1,2)],4)=>2
([(0,3),(1,2),(2,3)],4)=>2
([(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)],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)=>1
([],5)=>1
([(3,4)],5)=>2
([(2,4),(3,4)],5)=>2
([(1,4),(2,4),(3,4)],5)=>2
([(0,4),(1,4),(2,4),(3,4)],5)=>2
([(1,4),(2,3)],5)=>3
([(1,4),(2,3),(3,4)],5)=>2
([(0,1),(2,4),(3,4)],5)=>3
([(2,3),(2,4),(3,4)],5)=>2
([(0,4),(1,4),(2,3),(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)],5)=>2
([(0,4),(1,2),(1,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)=>3
([(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)],5)=>2
([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>2
([(0,4),(1,3),(2,3),(2,4)],5)=>3
([(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,3),(0,4),(1,2),(1,4),(2,3)],5)=>3
([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5)=>3
([(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)=>2
([(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)=>3
([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(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)=>2
([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>1
([],6)=>1
([(4,5)],6)=>2
([(3,5),(4,5)],6)=>2
([(2,5),(3,5),(4,5)],6)=>2
([(1,5),(2,5),(3,5),(4,5)],6)=>2
([(0,5),(1,5),(2,5),(3,5),(4,5)],6)=>2
([(2,5),(3,4)],6)=>3
([(2,5),(3,4),(4,5)],6)=>2
([(1,2),(3,5),(4,5)],6)=>3
([(3,4),(3,5),(4,5)],6)=>2
([(1,5),(2,5),(3,4),(4,5)],6)=>2
([(0,1),(2,5),(3,5),(4,5)],6)=>3
([(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,5),(2,5),(3,4),(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
([(2,4),(2,5),(3,4),(3,5)],6)=>2
([(0,5),(1,5),(2,4),(3,4)],6)=>3
([(1,5),(2,3),(2,4),(3,5),(4,5)],6)=>2
([(0,5),(1,5),(2,3),(3,4),(4,5)],6)=>3
([(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(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)=>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)=>3
([(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)=>2
([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(1,4),(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)=>3
([(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)=>2
([(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)=>3
([(1,5),(2,4),(3,4),(3,5)],6)=>3
([(0,1),(2,5),(3,4),(4,5)],6)=>3
([(1,2),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(2,3),(3,5),(4,5)],6)=>3
([(1,4),(2,3),(2,5),(3,5),(4,5)],6)=>3
([(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)=>3
([(1,4),(1,5),(2,3),(2,5),(3,4)],6)=>4
([(0,5),(1,4),(2,3),(2,4),(3,5),(4,5)],6)=>2
([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,2),(1,4),(2,3),(3,5),(4,5)],6)=>3
([(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(2,3),(3,4),(3,5),(4,5)],6)=>4
([(0,5),(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(2,3),(2,4),(3,5)],6)=>3
([(0,1),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,5),(1,5),(2,3),(2,4),(3,4)],6)=>3
([(0,4),(1,2),(1,3),(2,5),(3,5),(4,5)],6)=>3
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5)],6)=>3
([(0,4),(1,2),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,1),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(1,4),(2,3),(2,5),(3,5),(4,5)],6)=>3
([(0,3),(0,4),(1,2),(1,5),(2,5),(3,5),(4,5)],6)=>3
([(0,3),(1,4),(1,5),(2,4),(2,5),(3,5),(4,5)],6)=>3
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,1),(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,3),(0,5),(1,3),(1,5),(2,4),(2,5),(3,4),(4,5)],6)=>3
([(0,3),(1,4),(1,5),(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)=>3
([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,4),(1,5),(2,3),(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)],6)=>3
([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(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)=>2
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6)=>2
([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>3
([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>3
([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(2,5),(3,4)],6)=>3
([(0,3),(0,5),(1,2),(1,5),(2,4),(3,4),(4,5)],6)=>3
([(0,5),(1,2),(1,4),(2,3),(3,4),(3,5),(4,5)],6)=>3
([(0,1),(0,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,5),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,1),(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(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)=>2
([(0,4),(0,5),(1,2),(1,4),(2,3),(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)=>4
([(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)=>2
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)],6)=>2
([(0,1),(0,2),(0,3),(1,4),(1,5),(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)],6)=>3
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(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)=>2
([(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)=>3
([(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)=>2
([(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)=>2
([(0,1),(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,2),(1,3),(2,3),(2,5),(3,4),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)],6)=>3
([(0,3),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(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)=>2
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,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)=>2
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4)],6)=>3
([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,3),(0,4),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>3
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>4
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,4)],6)=>3
([(0,1),(0,3),(0,5),(1,2),(1,4),(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),(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)=>2
([(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)=>2
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(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)=>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)=>2
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,1),(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>3
([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(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)=>2
([(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)=>1
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 lettericity of a graph.
Let $D$ be a digraph on $k$ vertices, possibly with loops and let $w$ be a word of length $n$ whose letters are vertices of $D$.
The letter graph corresponding to $D$ and $w$ is the graph with vertex set $\{1,\dots,n\}$ whose edges are the pairs $(i,j)$ with $i < j$ sucht that $(w_i, w_j)$ is a (directed) edge of $D$.
Let $D$ be a digraph on $k$ vertices, possibly with loops and let $w$ be a word of length $n$ whose letters are vertices of $D$.
The letter graph corresponding to $D$ and $w$ is the graph with vertex set $\{1,\dots,n\}$ whose edges are the pairs $(i,j)$ with $i < j$ sucht that $(w_i, w_j)$ is a (directed) edge of $D$.
References
[1] Petkovšek, M. Letter graphs and well-quasi-order by induced subgraphs MathSciNet:1844046
Code
# very silly code, see Petkovšek for a characterisation
def letter_graph(w, D):
"""
INPUT:
- w, a word of length n with letters being vertices of D
- D, a digraph, loops allowed
OUTPUT:
- a k-letter graph with n vertices
"""
n = len(w)
E = [(i,j) for i in range(n) for j in range(i) if D.has_edge(w[i], w[j])]
return Graph([list(range(n)), E])
from sage.misc.lazy_list import lazy_list
from sage.databases.findstat import FindStatCollection
@cached_function
def letter_graphs(n, k):
"""
The set of all k-letter graphs with n vertices.
"""
n_graphs = FindStatCollection(20).levels_with_sizes()
c_graphs = set()
def graph_iterator():
c_digraphs = set()
for L in subsets(range(k)):
for Ds in digraphs(k):
D = DiGraph([Ds.vertices(), Ds.edges() + [(l,l) for l in L]], loops = True)
D = D.canonical_label().copy(immutable=True)
if D in c_digraphs:
continue
c_digraphs.add(D)
for w in Words(alphabet=D.vertices(), length=n):
G = letter_graph(w, D).canonical_label().copy(immutable=True)
if G not in c_graphs:
c_graphs.add(G)
yield(G)
if n in n_graphs and len(c_graphs) == n_graphs[n]:
return
return lazy_list(graph_iterator())
def statistic(G):
G = G.canonical_label().copy(immutable=True)
n = G.num_verts()
for k in range(1, n+1):
if G in letter_graphs(n, k):
return k
Created
Jul 09, 2021 at 12:04 by Martin Rubey
Updated
Jul 09, 2021 at 12:04 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!