Co-funded by:
Mentored by:

Traversability of vertex-transitive graphs

Coordinator of the project: University of Primorska, Andrej Marušič Insitute (Slovenia).

Partner organisations: InnoRenew CoE Renewable Materials and Healthy Environments Research and Innovation Centre of Excellence (Slovenia); University of Primorska, Faculty of mathematics, Natural Sciences and Information Technologies (Slovenia); University of Ljubljana, Faculty of Education (Slovenia).

Project Summary

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«

– algorithmic development and implementation for generating vertex-transitive graphs with given properties,

– algorithmic development and implementation for searching Hamiltonian paths and cycles in particular vertex-transitive graphs.