To "warm up" for the event a Graph Theory Seminar will be held at the University of Southern Denmark the day before, Thursday January 17, 2002, starting at 11.15AM in Auditorium 95.
We hereby invite all interested to take part in the seminar and attend
the defence.
PRELIMINARY LIST OF PARTICIPANTS : Lars Døvling Andersen,
Jørgen Bang-Jensen, John Adrian Bondy, Mette Hagenborg Eskesen, Gregory Gutin, Ron Gould,
Michael A. Henning, Leif Kjær Jørgensen, Jens Myrup, Michael Stiebitz, Carsten Thomassen, Jakob Peter Thomsen,
Bjarne Toft, Preben Dahl Vestergaard, Anders Yeo.
AT THE DEFENCE also Oleg Borodin and Tommy R. Jensen will be present.
*************************************
PROGRAM JANUARY 17, 2002, IN U95:
11.15-11.30 Welcome (Bjarne Toft)
11.30-12.00 First lecture (Preben Dahl Vestergaard)
Domination parameters in a graph
12.15-12.45 Second lecture (Michael A. Henning)
Defending the Roman Empire from multiple attacks
12.45-13.30 Lunch
13.30-14.00 Third lecture (Ron Gould)
Partitioning Vertices of a Tournament into Independent Cycles
14.15-14.45 Fourth lecture (Anders Yeo)
Decomposing k-arc strong tournaments into arc-disjoint strong subgraphs
15.00-15.30 Fifth lecture (Gregory Gutin)
Why assigning and travelling persons should not be greedy
15.30-16.15 Coffee break
16.15-16.45 Sixth lecture (Michael Stiebitz)
Partitions of graphs
17.00-17.30 Seventh lecture (Carsten Thomassen)
Classification of locally 2-connected compact metric spaces
17.45-18.15 Eighth lecture (Adrian Bondy)
Short proofs of classical theorems
18.30-20.00 Dinner
**************************************
**************************************
RON GOULD
Partitioning Vertices of a Tournament into Independent Cycles
with G. Chen and H. Li
Abstract: Let k be a positive integer. A strong digraph G is termed
k-connected if the removal of any set of fewer than k vertices results
in a strongly connected digraph. The purpose of this paper is to show
that every k-connected tournament with at least 8k vertices contains
k
vertex-disjoint directed cycles spanning the vertex set. This result
answers a question posed by Bollobás.
***************************************
GREGORY GUTIN
Why assigning and travelling persons should not be greedy
The greedy algorithm and its variations are often used in optimisation
theory and practice. It is well-known that the greedy algorithm (GA)
will always compute an optimal solution only for some very special
optimisation problems, matroids.
Nevertheless, it has been intuitively thought that GA computes
"good" solutions for non-matroidal problems (and it has been "confirmed"
by some theoretical and experimental
results).
Our results show the opposite: GA should be avoided if we are
dealing with the NP-hard travelling salesman problem or, even, the
polynomial time solvable assignment
problem. We prove that for either problem, for any size n ,
there exists an instance of the problem for which GA will find the
unique worst possible solution. (For either problem,
there are fast algorithms without this property.) We call such
problems anti-matroids and study a special class of anti-matroids,
I-anti-matroids, that includes the travelling
salesman and assignment problems.
Joint work with Anders Yeo
*****************************************
ANDERS YEO
TITLE: Decomposing k-arc strong tournaments into arc-disjoint strong subgraphs
ABSTRACT:
A tournament, is an orientation of a complete graph. k-arc-strong
means that the digraph is strong (i.e. there is an (x,y)-path and
a (y,x)-path for all distinct vertices x and y) whenever
we delete at most (k-1) arcs. We will talk about the following conjecture
and results (n denotes the number of vertices):
[1.] We conjecture that every k-arc-strong tournament contains
k arc-disjoint spanning strong subdigraphs.
[2.] If D=(V,A) is a 2-arc-strong semicomplete digraph,
then it contains 2 arc-disjoint spanning strong subdigraphs except for
one digraph on 4 vertices.
[3.] Every k-arc-strong tournament with minimum in- and out-degree
at least 37k contains k arc-disjoint
strong spanning subdigraphs.
[4.] Every k-arc-strong tournament contains a spanning
k-arc-strong subdigraph with no more than nk+280k^2 arcs. Note
that any k -arc-strong digraph has at least nk arcs, as every
vertex has at least k arcs out of it.
[5.] We give a construction which shows that for each k
>= 2 there are k -arc-strong tournaments on n vertices
such that every k-arc-strong spanning subdigraph of T contains at
least nk + \frac{k(k-1)}{2} arcs.
Note that the conjecture mentioned in 1, would imply the well-known Kelly-conjecture. The result in 2 implies that the conjecture in 1 is true for k=2.
We will furthermore state a number of useful lemmas, and a number of
conjectures. nd we will talk about how the above results relate to
out- and in-branchings in tournaments.
******************************************
MICHAEL STIEBITZ
Abstract:Let p be a given graph parameter and let
s,t \geq 1 be integers. Does there exists a
number f(s,t) such that every graph with
p(G) \geq f(s,t) (or p(g) \leq f(s,t)) has a
partition (A,B) of the vertex set V(G) such
that g(G(A)) \geq s and p(G(B)) \geq t
(or p(G(A))\leq s and p(G(B)) \leq t)?
We will discuss this question for several graph
parameters.
******************************************
MICHAEL A. HENNING
Defending the Roman Empire from multiple attacks
Abstract: We present a graph theoretic approach to defending the Roman Empire from multiple attacks by stationing as few legions as possible.
*******************************************
This page was last modified on Jan. 16, 2002, by Bjarne Toft