edit this statistic or download as text // json
Identifier
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
click to show known generating functions       
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$.
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