Parikh word representability of bipartite permutation graphs

DOI10.1016/J.DAM.2019.12.005zbMATH Open1441.05165arXiv1812.10251OpenAlexW2997844190WikidataQ126526660 ScholiaQ126526660MaRDI QIDQ2185746FDOQ2185746

Authors: Wen Chean Teh, Zhen Chuan Ng, M. Javaid, Zi Jing Chern 

Publication date: 5 June 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: The class of Parikh word representable graphs were recently introduced. In this work, we further develop its general theory beyond the binary alphabet. Our main result shows that this class is equivalent to the class of bipartite permutation graphs. Furthermore, we study certain graph theoretic properties of these graphs in terms of the arity of the representing word.

Full work available at URL: https://arxiv.org/abs/1812.10251

Recommendations

• Structural properties of word representable graphs
• Some results on Parikh word representable graphs and partitions
• On representable graphs
• Word-Representable Graphs: a Survey

zbMATH Keywords

Hamiltonian cyclediameterParikh matricesbipartite permutation graphParikh word representable graph

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Graph representations (geometric and intersection representations, etc.) (05C62) Combinatorics on words (68R15)

Cites Work

• Statistical problems involving permutations with restricted positions
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• On a conjecture about Parikh matrices
• A sharpening of the Parikh mapping
• On core words and the Parikh matrix mapping
• On Context-Free Languages
• Bipartite permutation graphs
• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• Computing the Minimum Fill-In is NP-Complete
• Words and graphs
• Interval bigraphs and circular arc graphs
• Structural properties of word representable graphs
• Interval \(k\)-graphs and orders
• Characterizations for unit interval bigraphs
• Characterizing intersection classes of graphs
• Elementary matrix equivalence and core transformation graphs for Parikh matrices
• On strongly \(M\)-unambiguous prints and Şerbǎnuţǎ's conjecture for Parikh matrices
• Order of weak \(M\)-relation and Parikh matrices
• On the switch Markov chain for perfect matchings

Cited In (8)

• Parikh word representable graphs and morphisms
• Critical properties of bipartite permutation graphs
• Word-representability of graphs with respect to split recomposition
• Some results on Parikh word representable graphs and partitions
• Counting subwords in circular words and their Parikh matrices
• Certain distance-based topological indices of Parikh word representable graphs
• Structural properties of word representable graphs
• Erasure and error correcting ability of Parikh matrices

This page was built for publication: Parikh word representability of bipartite permutation graphs

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