Counting word-representable digraphs with a prescribed number of strong components
Counting word-representable digraphs with a prescribed number of strong components
Let an -word be a word of length over an -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 -words over an -alphabet, with a unique factorisation, that represent word-graphs with strong components is the number of -partitions of an -set with disjoint proper subsets of parts whose union is a set of the form . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.