Graph Theory

Graph Theory

Graph Theory

The mathematical subject of graph theory serves as a model for physical networks as well as abstract relations between objects, e.g. in mathematics, computer science or in social networks.

This research group also covers association schemes, latin squares and combinatorial designs. These combinatorial objects have relations to graphs, in particular to graphs with some degree of structure.

Recently the group has focused on the degree/diameter problem. This graph theory problem has applications in designing the topology of communication networks with high transmission speed (low diameter) and low cost (number of connections). The goal is to construct large graphs with a given degree and diameter and to prove better upper bounds on the order of the graph.

The study of graphs and digraphs with given degree and diameter and order close to the trivial upper bound, known as the Moore bound, leads to graphs with a structure similar to strongly regular graphs. Directed strongly regular graphs have been the subject of an increasing number of research papers in the past few years.

In these subjects combinatorial methods from graph theory are often combined with algebraic methods. Computer enumeration also plays an increasing role in this research area.

Topics of recent and current interest includes

  • large graphs and digraphs with small degree and diameter.
  • small graphs with large degree and girth.
  • construction of association schemes with few classes, including strongly regular graphs and their orientation.
  • directed strongly regular graphs.
  • normally regular graphs.