Postgraduate research opportunities Graph representations

Apply

Key facts

  • Opens: Tuesday 31 March 2020
  • Number of places: 1
  • Duration: 3 - 4 years

Overview

Graph representations became crucial with the advent of the computer era for storing graphs in computer memory. However, graph representations, e.g. those involving patterns in words, are also useful in solving problems on graphs as they may allow transferring a graph problem to that on other objects hence solving it.
Back to opportunity

Eligibility

BSc or MSc in mathematics or computer science is required.

THE Awards 2019: UK University of the Year Winner
Back to opportunity

Project Details

Graph representations became crucial with the advent of the computer era for storing graphs in computer memory, so the question of finding efficient representations of graphs is definitely timely. However, graph representations are also interesting and useful in solving (hard) problems on graphs. Indeed, certain representations may allow one to transfer a graph problem to a problem on objects representing the graphs, then solving the problem on those objects and returning a solution on the graphs. For example, in 1918, Heinz Prüfer discovered a fascinating relationship between labelled trees with n vertices and sequences of length n-2 made of the elements of the set {1,2,…,n}. This relationship is a bijection and it allowed Prüfer to prove Cayley’s formula for the number of n-vertex labelled trees. In this project, we will focus on various ways to represent graphs on n vertices using words (i.e. strings of symbols) over an alphabet {1,2,…,n}. In particular, in the studies, we will deploy certain graph orientations helping us with representation questions, and also use patterns in words.  

Back to opportunity

Supervisors

Dr Sergey Kitaev

Reader
Mathematics and Statistics

View profile
Back to course

Apply

Please email Dr Sergey Kitaev (sergey.kitaev@strath.ac.uk) if you would like to apply for this opportunity.