Abstract :

The oldest connection of words and graphs can be found in Prüfer sequences. 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, in fact, a bijection between trees and the sequences, and it allowed Prüfer to prove Cayle's formula about the number of n-vertex labelled trees. The Prüfer sequence is a classical example showing the importance of words for graph enumeration. More importantly, with the advent of the computer era, representing graphs by words became crucial for storing graphs in computer memory. Words have also been used to reveal and describe various useful properties of graphs. We will discuss a few examples of such interactions of words and graphs from the literature. The talk will be elementary.