Session I.3 - Graph Theory and Combinatorics
Poster
A polynomial-time algorithm to find a minimal word representing a tree permutationally
Khyodeno Mozhui
Indian Institute of Technology Guwahati, India - This email address is being protected from spambots. You need JavaScript enabled to view it.
A word-representable graph is a simple graph $G$ that can be represented by a word $w$ over its vertices such that any two vertices are adjacent in $G$ if and only if they alternate in $w$. The class of comparability graphs, i.e., the graphs which admit a transitive orientation, play a vital role in the theory of word-representable graphs. The class of comparability graphs is precisely the class of graphs that can be represented by a concatenation of permutations of their vertices. The minimum number of such permutations of vertices of a comparability graph is its permutation-representation number. Finding the permutation-representation number of a comparability graph is NP-hard. Hence, finding the permutation-representation number of certain special classes of comparability graphs is of interest in the literature. The permutation-representation number of bipartite graphs is an open problem. In this work, we study the permutation-representation number of a special class of bipartite graphs, viz. trees. In this connection, we devise a polynomial-time algorithm to construct a minimal word that represents a given tree permutationally. Accordingly, we provide the permutation-representation number of trees.
Joint work with K. V. Krishna (Indian Institute of Technology Guwahati, India).