Postgraduate research opportunities Graph representations


Key facts

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


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


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


Dr Sergey Kitaev

Mathematics and Statistics

View profile
Back to course


Please email Dr Sergey Kitaev ( if you would like to apply for this opportunity.

Number of places: 1

To read how we process personal data, applicants can review our 'Privacy Notice for Student Applicants and Potential Applicants' on our Privacy notices' web page.