GRAPH THEORY SEMINAR AT SDU ODENSE, JANUARY 17, 2002.

DOCTORAL DEFENCE AT SDU ODENSE, JANUARY 18, 2002

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