Encoding graphs by words and morphisms

Rights statement
Awarding institution
  • University of Strathclyde
Date of award
  • 2021
Thesis identifier
  • T16078
Person Identifier (Local)
  • 201893638
Qualification Level
Qualification Name
Department, School or Faculty
  • This thesis is related to encoding graphs by words, where we deal with so called word representation of graphs, relevant to them semi-transitive orientations, and more exotic ways to represent graphs via bijections with certain words and pattern-avoiding 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 word-representation of such graphs. A particular result obtained by us that goes beyond the study of split graphs, is a characterization of word-representable graphs in terms of permutations of columns of the adjacency matrices. We also provide a complete classification of word-representable 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 semi-transitively (i.e. are semi-transitive) or a finite iteration k of the morphism produces a non-semi-transitive orientation (which will stay non-semi-transitive for all iterations > k). We fully classify semi-transitive infinite directed split graphs in question. In Chapter 4, we present encoding p-Riordan graphs by p-Riordan words, and encoding Riordan graphs by pattern-avoiding permutations. Also, we encode oriented Riordan graphs by balanced words over the alphabet {0, 1, 2}, and provide, as a bi-product, a proof of a known enumerative result about closed walks in the 3-cube.
Advisor / supervisor
  • Kitaev, Sergey, 1975-
Resource Type