Jørgen Bang-Jensen will defend his doctoral thesis "Digraphs : Theory and Algorithms", submitted to the University of Southern Denmark, on Friday January 18, 2002, at 1.15 PM. Official opponents at the defence are John Adrian Bondy and Ron Gould. The defence takes place in Auditorium 100 at the University of Southern Denmark in Odense.

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.


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




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.


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
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


TITLE: Decomposing k-arc strong tournaments into arc-disjoint strong subgraphs

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.


Partitions of graphs

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.


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