PAST RESEARCH

Graph symmetries:

Our aim is to develop a theory for transitive graphs that can be seen as a graph-theoretical analogue of the Bass-Serre-theory for groups.

Stallings' splitting theorem is one of the crucial theorems in geometric\combinatorial group theory. It says a finitely generated group with more than one end is either an amalgamated free product, or a HNN extension over a finite subgroup. Hamann, Lehner, Rühmann, and I recently proved an analogous result for infinite graphs and I am currently working on its applications.

One of the applications of Stallings' theorem is accessibility. A finitely generated group G is said to be accessible if the process of iterated nontrivial splitting of G by Stalllings' theorem always terminates in a finite number of steps. Recently Hamann and I proved an analogous result for accessible graphs.

Spanning subgraphs in Cayley (di)graphs:

This project splits into two parts. In the first part, we study the decomposition of the Cartesian product of two directed cycles into two arc-disjoint  hamiltonian dipaths. This can be considered as the decomposition of the Cayley digraph of two cyclic groups with the standard generating set. I am interested in the general case of whether any Cayley digraph of two cyclic groups can be decomposed into two arc-disjoint hamiltonian dipaths.

The next part is about hamiltonicity of infinite Cayley graphs.  The notion of topological circles of a graph has made it possible to extend theorems about cycles in finite graphs to locally finite graphs with ends. In particular, the existence of a hamiltonian circle, a topological circle in |Cay(G,S)| that passes through every vertex and every end is an open question. I am interested in Cayley graphs with hamiltonian circles.

Median-decompositions:

Treewidth can be seen as a measure of how “treelike” a graph is. The usefulness of tree decompositions as a decomposition tool, especially in the theory of Graph Minors, is highlighted by various structural theorems and  several NP-hard decision and optimization problems are fixed-parameter tractable when parameterized by treewidth. 

Since graphs of bounded treewidth inherit several advantages of trees, it is very natural to investigate how to go beyond tree-decompositions and try to model a graph on graphs other than trees. One of these approaches is median-decompositions which are originally introduced for graphs by Konstantinos Stavropoulos as a generalization of tree-decompositions. 

In this project, we investigate different aspects of median-decompositions including algorithmic aspects.