Bobby Babak Miraftab
Who is this guy?
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.
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.
Man muß jederzeit an Stelle von „Punkte, Geraden, Ebenen“ „Tische, Stühle, Bierseidel“ sagen können. [One must always be able to say “tables, chairs, beer mugs” in place of “points, lines, planes”.]