- PROJECT CODE: J1-9110 (B)
- PROJECT TITLE: Traversability of vertex-transitive graphs
- PROJECT TEAM: Klavdija Kutnar, PhD / Miklós Krész, PhD (leader for InnoRenew CoE), Michael David Burnard
- PERIOD: 01.07.2018 – 30.06.2021
- FTE: 0.1 FTE for InnoRenew CoE in 2020
- FINANCING: Slovenian Research Agency (ARRS)
- PROJECT COORDINATOR: University of Primorska, Andrej Marušič Insitute (Slovenia)
- PARTNERS: InnoRenew CoE (Slovenia); University of Primorska, Faculty of Mathematics, Natural Sciences and Information Technologies (Slovenia); University of Ljubljana, Faculty of Education (Slovenia)
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 project activities
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.
