seminario Prof.Marusic

[Emilia Mezzetti]

Martedì 27 marzo 2012, alle ore 16:00,
presso l'aula Morin del Dipartimento di Matematica e Geoscienze,
(ed. H2/bis, II piano)

il prof. Dragan Marusic
(Rettore della Univerza na Primorskem - 
Università del Litorale, Koper - Capodistria)

terrà un seminario dal titolo:

Hamiltonicity of vertex-transitive graph

Abstract:

A path (cycle) containing every vertex in a graph 
is called a {\em Hamilton path}
({\em Hamilton cycle,} respectively). Hamilton 
cycles have been studied extensively in graph
theory for their own sake, because of connections 
with the four color problem, and the travelling
salesman problem. A graph is called {\em 
vertex-transitive} if for any pair of vertices 
$u$ and
$v$ there exists an automorphism mapping $u$ to 
$v$. In 1969, Lovasz asked whether every
finite connected vertex-transitive graph has a 
Hamilton path, thus tying together two seemingly
unrelated concepts: traversability and symmetry 
of graphs. With the exception of the complete
graph on two vertices, only four connected 
vertex-transitive graphs that do not have a 
Hamilton
cycle are known to exist. These four graphs are 
the Petersen graph, the Coxeter graph and the
two graphs obtained from them by replacing each 
vertex by a triangle. The fact that none of these
four graphs is a Cayley graph has led to a 
folklore conjecture that every Cayley graph has a 
Hamilton
cycle. (A Cayley graph is a graph whose 
automorphism group admits a regular subgroup.)
Both of these two problems are still open. 
However, a considerable amount of partial results
are known. In this talk an overview of these 
results will be introduced. A special emphasis
will be given to recent results concerning the 
existence of Hamilton cycles in cubic Cayley
graphs arising from groups having $(2,s,3)$-presentation.


Prima del seminario il prof. Marusic insieme ad alcuni colleghi
della sua Università presenterà brevemente l'attività del
del Dipartimento di Matematica della Univerza na Primorskem
in programma per l'anno 2012.

Tutti gli interessati sono invitati a partecipare.

-- 
Prof. Emilia Mezzetti

Dipartimento di Matematica e Geoscienze
Sezione di Matematica e Informatica
Universita' di Trieste
Via Valerio 12/1
34127 Trieste, Italia

Stanza 227, II piano
e-mail: mezzette at units.it
tel. studio (+39) 040 558 2650
skype: emiliamezzetti
tel. Segreteria Dip.: (+39) 040 558 2635
fax: (+39) 040 558 2636
http://www.dmi.units.it/~mezzette/