Hamiltonski cikli v točkovno tranzitivnih grafih / Hamilton cycles in vertex-transitive graphs
|
Naziv Tittle |
Hamiltonski cikli v točkovno tranzitivnih grafih / Hamilton cycles in vertex-transitive graphs |
|
Akronim Acronim |
Z1-4006 |
|
Opis Description |
(SI) Cilj predlaganega projekta so novi rezultati na problemu hamiltnoskost točkovno tranzitivnih grafov (HPC problem). Natančneje, rešiti HPC problem za posebne neskončne družine točkovno tranzitivnih grafov in Cayleyjevih grafov z restrikcijami na posebne rede, posebne valence in posebna delovanja grupe avtomorfizmov. Najprej bomo končali že začete raziskave: HPC problem za kubične CG grup G z (2,s,3) -prezentacijo, t.j. G=(a,x . a2= xs=(ax)3=1, …); HPC problem za točkovno tranzitivne grafe reda pq, p in q praštevili. Potem bomo obravnavali HPC problem za točkovno tranzitivne grafe reda pk, p praštevilo, in drugih posebnih redov kot tudi za Cayleyjeve grafe grup z (2,s,t) –prezentacijo (posplošitev zgornjega rezultata). Med predlaganim projektom bodo obravnavani tudi drugi problemi povezani s točkovno tranzitivnimi grafi, kot so odprt problem polregularnosti (Marušič, 1981), strukturne lastnosti točkovno tranzitivnih grafov in lastnosti grup avtomorfizmov. Namreč, pogosto uporabljena metoda za iskanje hamiltonskih ciklov v točkovno tranzitivnih grafih sloni na kvocientiranju glede na neprimitivnostni sistem blokov grupe avtomorfizmov ali glede na polregularen avtomorfizem (Metoda dviga). Pri raziskovanju HPC problema za kubične Cayleyjeve grafe bomo posplošili inovativno metodo - metodo Hamiltonskih dreves na ploskvah. Med drugim bomo uporabljali tudi rezultate iz splošne teorije grafov, kombinatorične tehnike skupaj z njihovo uporabo v teoriji permutacijskih grup in algebraične metode. (EN) 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. |
|
Vrsta projekta Project Type |
Podoktorski projekt |
|
Trajanje Duration |
01/07/2011 - 30/06/2013 |
|
URL URL |
https://www.sicris.si/public/jqm/prj.aspx?lang=slv&opdescr=search&opt=2&subopt=400&code1=cmn&code2=auto&psize=10&hits=1&page=1&count=&search_term=Z1-4006&id=7110&slng=&order_by= |
|
Vodja projekta Project Leader |
Klavdija Kutnar |
|
Sodelujoče organizacije Participating organizations |
/ |
|
Oddelek Department |
Oddelek za matematiko IAM |