Postgraduate research opportunities Graph representations

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.