Co-funded by:
Mentored by:

Traversability of vertex-transitive graphs

Summary of the project

Graph theory is one of the most important research areas in discrete mathematics. Mostly because graphs provide optimal models of different real-life situations. For example, in the natural and social sciences, they model relations among societies, companies, etc. In computer science, they represent networks of communication, data organization, computational devices, and more. In statistical physics, graphs can represent local connections between interacting parts of a system. And finally, in mathematics, since graphs carry a natural metrics, they are useful in geometry and topology as well as in group theory specifically via the so-called Cayley graphs which naturally arise from groups. In various applications of graphs, one often finds that graphs exhibiting optimal behaviour are highly symmetric structures, that is, admitting a large automorphism group. Highly symmetric structures considered in this proposal are vertex-transitive graphs with special emphasis given to Cayley graphs, the idea of which was invented in the 19th century in order to investigate properties of groups. The main property considered in this proposal is traversability with special emphasis given to the existence of Hamiltonian cycles and paths.  

InnoRenew CoE main activities in the project 

We will develop and implement algorithms for generating vertex-transitive graphs with given properties and focus on algorithmic development and implementation for searching Hamiltonian paths and cycles, in particular vertex-transitive graphs.

Bibliography