Counting word-representable digraphs with a prescribed number of strong components

Let an \ell-word be a word of length \ell over an nn-letter alphabet, and suppose it has a unique factorisation into factors corresponding to alphabet-disjoint partitions. A word-graph is the digraph represented by such a word, and a strong component is a maximal strongly connected subdigraph. Counting conjecture. The number of \ell-words over an nn-alphabet, with a unique factorisation, that represent word-graphs with kk strong components is the number of nn-partitions of an \ell-set with kk disjoint proper subsets of parts whose union is a set of the form j,j+1,,j+m{j,j+1,\ldots,j+m}. Each such union is an alphabet-disjoint partition in the corresponding representational word and is a strong component in the corresponding word-graph. This is presented as possible future work extending the paper's enumeration of strongly connected word-graphs; the text does not provide a proof or establish the asserted enumeration.

Sources & referencesView supporting material

Primary source

Edward J. L. Bell, Damon Berridge and Paul Rayson, “The strong-connectivity of word-representable digraphs”, arXiv:1102.0980 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.