Projects / Programmes
Hamilton cycles in vertex-transitive graphs
| Code |
Science |
Field |
Subfield |
| 1.01.05 |
Natural sciences and mathematics |
Mathematics |
Graph theory |
| Code |
Science |
Field |
| P110 |
Natural sciences and mathematics |
Mathematical logic, set theory, combinatories |
| Code |
Science |
Field |
| 1.01 |
Natural Sciences |
Mathematics |
Hamilton cycle, Hamilton path, vertex-transitive graph, Cayley graph
Researchers (1)
| no. |
Code |
Name and surname |
Research area |
Role |
Period |
No. of publicationsNo. of publications |
| 1. |
24997 |
PhD Klavdija Kutnar |
Mathematics |
Head |
2011 - 2013 |
251 |
Organisations (1)
Abstract
A path (cycle) containing every vertex in a graph is called a Hamilton path (Hamilton cycle). Hamilton cycles have been studied extensively in graph theory for their own sake, because of early connections with the four color problem, and the travelling salesman problem. A graph is called vertex-transitive if, for any two of its vertices u and v, one can find an automorphism mapping u to v. In 1969 Lovasz linked the two concepts with the following question: Does every connected vertex-transitive graph have a Hamilton path? Consideration of this question led to the next question: Does every connected Cayley graph have a Hamilton cycle? (A Cayley graph is a graph admitting a regular subgroup in its automorphism group.) In spite of over forty years of work on these two questions, both remain unsolved. However, an extensive body of partial results has been published. Some of these results were obtained by the proposed project leader in the course of her PhD training. The hamiltonicity of vertex-transitive graphs (HPC problem) concerns these two questions. The aim of the proposed project is to obtain future results on this topic; in particular, to answer these questions for special infinite families of vertex-transitive graphs and Cayley graphs regarding special orders, special valencies, and special types of the action of the automorphism group. Initially, research that has been in progress will be considered: the HPC problem for cubic CGs arising from groups with a (2,s,3)-presentation, that is, G=(a,x | a2 = xs = (ax)3 = 1, …) and the HPC problem for vertex-transitive graphs of order pq, p and q primes. Then the HPC problem will be considered for vertex-transitive graphs of order pk, p a prime, and other restrictions on the order of vertex-transitive graphs, as well as for Cayley graphs, arising from groups with (2,s,t) –presentation (generalization of the above result). During the proposed project other problems related to vertex-transitive graphs, such as the semiregularity problem (posed by Marušič in 1981 also still open), structural properties of vertex-transitive graphs and, in addition, properties of the automorphism groups of vertex-transitive graphs will be considered. Namely, a frequently used approach to constructing Hamilton cycles in vertex-transitive graphs is based on a quotienting with respect to an imprimitivity block system of the automorphism group or with respect to a semiregular automorphism (Lifting approach). For results on cubic Cayley graphs we will generalize the innovative method, known as Hamilton trees on surfaces approach. Also, many results from classical graph theory, combinatorial techniques and their use in permutation group theory, as well as a wide range of algebraic methods, will be used. The expected results are one of the most important next steps needed to be taken if one is to obtain a complete solution of the HPC problem. These findings will be published in International respected SCI journals which will help contribute to the international reputation of Slovenia in the field of mathematics.
Significance for science
The importance of the research results of the project can be seen from comprehensive world bibliography, and the citations of these results. The results of the project are one of the most important next steps needed to be taken if one is to obtain a complete solution of the problem of existence of Hamilton cycles and paths in vertex-transitive graphs. Also, they will potentially bear fruit in many other important open problems in the field of algebraic graph theory (such as, for example, the problem of the existence of semiregular automorphisms in vertex-transitive graphs and the problem of non-existence of Cayley snarks).
Significance for the country
With this project Slovenia kept in touch with modern trends in mathematics - in algebraic graph theory field. The results of the project were introduced at international scientific conferences, meetings and summer schools around the world, six times as invited/keynote lecture as well as at prestigious universities abroad (Vanderbilt University, FU Berlin, The University of the Basque Country, ...). With these the project contribute to promotion of Slovenian science around the world. The international integration of the project, and thus Slovenia, is also reflected in the attractiveness of the algebraic graph theory research group at the University of Primorska for its doctoral and postdoctoral training for foreigners (the researchers come from Hungary, China, USA, etc.).
Most important scientific results
Annual report
2011,
2012,
final report,
complete report on dLib.si
Most important socioeconomically and culturally relevant results
Annual report
2011,
2012,
final report,
complete report on dLib.si
