Some results on Parikh word representable graphs and partitions

Combinatorial aspects of partitions of integers (05A17) Graph theory (including graph drawing) in computer science (68R10) Combinatorics on words (68R15)

Review text

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.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Some results on Parikh word representable graphs and partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2423402)