Parikh word representability of bipartite permutation graphs

DOI10.1016/J.DAM.2019.12.005MaRDI QIDQ2185746zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

bipartite permutation graphdiameterHamiltonian cycleParikh matricesParikh word representable graph

Mathematics Subject Classification ID

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

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.

Recommendations

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

Cites work

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

Cited in

(9)

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

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)