This thesis is related to encoding graphs by words, where we deal with so called word representation of graphs, relevant to them semitransitive orientations, and more exotic ways to represent graphs via bijections with certain words and patternavoiding permutations. In Chapter 2, we introduce a way to define classes of split graphs via iterations of morphisms and present a number of general results on wordrepresentation of such graphs. A particular result obtained by us that goes beyond the study of split graphs, is a characterization of wordrepresentable graphs in terms of permutations of columns of the adjacency matrices. We also provide a complete classification of wordrepresentable split graphs defined by iteration of morphisms using two 2x2 matrices. In Chapter 3, we study families of directed split graphs obtained by iterations of morphisms applied to the adjacency matrices and giving as the limit infinite directed split graphs. For each of such a family we ask the question on whether all graphs in the family are oriented semitransitively (i.e. are semitransitive) or a finite iteration k of the morphism produces a nonsemitransitive orientation (which will stay nonsemitransitive for all iterations > k). We fully classify semitransitive infinite directed split graphs in question. In Chapter 4, we present encoding pRiordan graphs by pRiordan words, and encoding Riordan graphs by patternavoiding permutations. Also, we encode oriented Riordan graphs by balanced words over the alphabet {lcub}0, 1, 2{rcub}, and provide, as a biproduct, a proof of a known enumerative result about closed walks in the 3cube.
Date of Award  8 Nov 2021 

Original language  English 

Awarding Institution   University Of Strathclyde


Supervisor  Sergey Kitaev (Supervisor) & George Weir (Supervisor) 
