Minimum Length Word-Representants of Treelike Permutation Graphs
摘要
A simple graph is called a word-representable graph if there is a word over its vertex set such that any two vertices are adjacent in the graph if and only if they alternate in the word; such a word is called a word-representant of the graph. Srinivasan and Hariharasubramanian proved that a minimum length word-representant for a non-complete triangle-free circle graph on n vertices with at least one edge is of \(2n-2\) length. Further, they posed an open problem to find classes of word-representable graphs whose minimum length word-representants are of \(2n-\kappa \) length, where n is the number of vertices and \(\kappa \) is the clique number of a graph. A graph is called a treelike comparability graph if it admits a transitive orientation such that the transitive reduction is a tree. When such a graph is also a permutation graph, it is called a treelike permutation graph. Recently, a subclass of treelike permutation graphs, viz., the class of double-arborescences, was established to be the first example satisfying the criterion given in the above-mentioned open problem. In this work, we devise a polynomial-time algorithm to construct a minimum length word-representant for a given treelike permutation graph and show that all treelike permutation graphs satisfy the criterion of the open problem.