From: Kelli McGee \(Kelly Services Inc\) (a-kellim@microsoft.com)
Date: Wed May 12 2004 - 08:53:29 PDT
You are invited to attend... please pass on to internal MS employees who
may be interested.
************************************************************************
*****************************
WHO: Moshe Rosenfeld
AFFILIATION: University of Washington, Tacoma
TITLE: Variations on Hamiltonian Themes
WHEN: Mon 06/07/2004
WHERE: 113/1159 Research Lecture Room, Microsoft Research
TIME: 3:30PM-5:00PM
HOST: Laszlo Lovasz
************************************************************************
******************************
ABSTRACT:
The hunt for Hamilton Cycles in graphs started in the 18-th century.
Most probably Euler's search for a knight tour of the chess board was
the first Hamiton Cycle problem considered. Nowadays we are flooded by
theorems, conjectures, refuted conjectures, web sites whose common
characteristic is that if a graph satisfies P then it is Hamiltonian.
It is well known that the problem of finding a Hamilton Cycle in a graph
is "certifiably" difficult. As common among Mathematician, when the
going gets rough, the rough "change" the problem. Current trends are to
"refine"
(mutilate) the definition of Hamilton Cycle. The first very minimal
modification was to replace Hamiton Cycle by Hamilton Path. A more
drastic modification is to allow vertices to be visited more than once.
A 2-walk is a closed walk in a graph in which every vertex is visited
but not more than twice. A 3-tree is a tree with maximum degree 3.
Clearly, if G is Hamiltonian, it has a 2-walk but not vice versa. Thus,
instead of searching for Hamitonian cycles, several researchers, like M.
Ellingham, N. Wormald, F. Ruskey and others, proposed searching for
2-walks, or even k-walks. These modifications create a hierarchy among
graph properties:
Hamiltonian \subset Traceable \subset 2-walk \subset 3-tree \subset
3-walk...
In our work, we chose to retain the Hamilton Cycle and modify the graph.
Instead of searching for Hamilton Cycles in G we look for Hamilton
Cycles in the prism over G. This property is "sandwiched" between
"Hamiltonian" and 2-walk. With this in mind, we revisit many theorems,
conjectures, complexity problems etc. and test them for Hamilton Cycles
in the prism over G.
For instance, in the 19-th century it was "believed" that all cubic,
3-connected planar graphs are Hamiltonian. In 1946, Tutte constructed
the first counter example (with 46 vertices...). Is it true that the
prisms over these graphs are Hamiltonian? YES! On the other hand,
Nash-Williams conjectured that all 4-connected, 4-regular graphs are
Hamiltonian.
Infinitely many counter examples are known today. Such graphs clearly
have a 2-walk. Do they have a Hamiltonian Prism? The complexity of
determining whether a 4-connected, 4-regular graph is Hamiltonian is in
NPC. On the other hand, a 2-walk can be constructed in Polynomial time.
What about a Hamiltonian Cycle in the Prism?
In this talk I'll survey a sample of problems of this nature, and recent
results.
This is joint work with:
Daniel Kral (Charles University, Prague) Tomas Kaiser and Zdenek Ryjacek
(Western Bohemia, University, Pilzen) Heintz-Juergen Voss (Technical
University, Dresden).
BIO:
Moshe Rosenfeld was born in Israel. He received his Ph.D. from the
Hebrew University of Jerusalem. His Supervisors were Branko Grunbaum
and Michael Rabin. Professor Rosenfeld has taught at Ben Gurion
University in Israel, SFU in Canada, Charles University in Prague
(Senior Fulbright Scholar). He is currently a Professor at the
Institute of Technology, University of Washington, Tacoma. His
interests are Graph Theory and Combinatorial Geometry.
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Wed May 12 2004 - 08:54:48 PDT