Abstract
In this thesis we give a complete classification of semicomplete digraphs which have
an outbranching with root u which is arcdisjoint from some inbranching with root v
where u, v are prescribed vertices. Such a pair of branchings is called a good (u, v)pair.
Using this characterization, we completely solve the problem of deciding whether a given
digraph obtained by substituting the vertices of a semicomplete digraph with arbitrary
digraphs has a good (u, v)pair for given vertices u, v. This solves an open problem by
BangJensen and Gutin for quasitransitive digraphs from 1998. We also describe several
results concerning the existence of good pairs in digraphs whose complement is bipartite.
In addition, we study the problem of decomposing the arcs of a split digraph D into two arcdisjoint subsets such that both of which induce a strongly connected spanning digraph of D. In particular, we prove that every 3arcstrong split digraph has such an arcdecomposition. This confirms a conjecture of BangJensen and Yeo on decomposing digraphs with high arcconnectivity into strongly connected spanning subdigraphs for the special case where the digraph is a split digraph. We also provide infinite classes of 2 strong split digraphs with no good (u, v)pairs for some given u and v. Moreover, our results imply that Thomassen’s Conjecture on good (u, v)pairs in digraphs with high arcconnectivity holds for the five classes of digraphs mentioned above with arcconnectivity 3.
If a digraph D has a good (u, v)pair, then for every vertex w of D it is the case that D has a (w, v)path which is arcdisjoint from some outbranching rooted at u. It turns out that this partial problem also has a very natural characterization for semicomplete digraphs. In the characterization of semicomplete digraphs with a good (u, v)pair for given roots u, v, the existence of arcdisjoint (s1, t1) and (s2, t2)paths plays an important role. Motivated by this, in the thesis we also study the problem of finding arcdisjoint paths with specified endvertices in semicomplete digraphs and extend this result to mixed graphs.
Another topic in this thesis is structural and algorithmic properties of generalized paths and cycles in semicomplete multipartite digraphs. We show how these results allow us to identify classes of directed 01 TSP instances that can be solved in polynomial time as well as others for which we can get very close to the optimum in polynomial time. All our arguments in the thesis leading to the proofs of our results are constructive and can be converted to polynomial algorithms.
In addition, we study the problem of decomposing the arcs of a split digraph D into two arcdisjoint subsets such that both of which induce a strongly connected spanning digraph of D. In particular, we prove that every 3arcstrong split digraph has such an arcdecomposition. This confirms a conjecture of BangJensen and Yeo on decomposing digraphs with high arcconnectivity into strongly connected spanning subdigraphs for the special case where the digraph is a split digraph. We also provide infinite classes of 2 strong split digraphs with no good (u, v)pairs for some given u and v. Moreover, our results imply that Thomassen’s Conjecture on good (u, v)pairs in digraphs with high arcconnectivity holds for the five classes of digraphs mentioned above with arcconnectivity 3.
If a digraph D has a good (u, v)pair, then for every vertex w of D it is the case that D has a (w, v)path which is arcdisjoint from some outbranching rooted at u. It turns out that this partial problem also has a very natural characterization for semicomplete digraphs. In the characterization of semicomplete digraphs with a good (u, v)pair for given roots u, v, the existence of arcdisjoint (s1, t1) and (s2, t2)paths plays an important role. Motivated by this, in the thesis we also study the problem of finding arcdisjoint paths with specified endvertices in semicomplete digraphs and extend this result to mixed graphs.
Another topic in this thesis is structural and algorithmic properties of generalized paths and cycles in semicomplete multipartite digraphs. We show how these results allow us to identify classes of directed 01 TSP instances that can be solved in polynomial time as well as others for which we can get very close to the optimum in polynomial time. All our arguments in the thesis leading to the proofs of our results are constructive and can be converted to polynomial algorithms.
Original language  English 

Awarding Institution 

Supervisors/Advisors 

Date of defence  2. Feb 2024 
Publisher  
DOIs  
Publication status  Published  17. Jan 2024 