Some results on Parikh word representable graphs and partitions (Q2423402)

Over a binary alphabet \(\{a,b\}\), the Parikh matrix of a word encodes the number of occurrences of \(a\)s, \(b\)s and subwords (or scattered factors) \(ab\). With a word \(w=a^{n_1}ba^{n_2}b\cdots ba^{n_k}b\) there is associated the partition (and thus a Ferrers diagram) \[(n_1+\cdots +n_k)+\cdots+(n_2+n_1)+n_1\] of the integer counting the number of occurrences of the subword \(ab\) in \(w\). With a word of length \(n\) there is associated a simple graph with \(n\) vertices where edges correspond to the occurrences of a subword \(ab\). Graphs obtained in this way are said to be \textit{Parikh word representable}. In this paper, the authors present some connections between binary words and integer partitions. They determine when two Parikh word representable graphs are isomorphic. Consequently, they express the number of non-isomorphic Parikh word representable graphs with a given number of edges. For such graphs they discuss conditions to be Eulerian, for the presence of a cycle, regularity and the question of when the property of word representability is preserved under elementary graph operations such as vertex or edge deletion and bipartite complement.