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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Minimum Length Word-Representants of Treelike Permutation Graphs

  • Tithi Dwary,
  • K. V. Krishna

摘要

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.