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

About 15 years old · traced to

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.

References

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.