In-tournaments and semicomplete multipartite digraphs (Q2756071)

This is the author's PhD dissertation. The thesis deals with cycle properties of in-tournaments and semicomplete multipartite digraphs as well as some connectivity properties of the later class. A digraph \(D= (V,A)\) is an in-tournament (an in-semicomplete digraph) if \(N^-(x)\) induces a tournament (a semicomplete digraph) for every vertex \(x\in V\). Here \(N^-(x)\) denotes the set of in-neighbours of the vertex \(x\). In-tournaments where introduced by the reviewer, \textit{J. Huang} and \textit{E. Prisner} [J. Comb. Theory, Ser. B 59, 267-287 (1993; Zbl 0794.05033)], where basic properties on the path and cycle structure of in-tournaments were derived. In-tournaments have also been studied under the name fraternately oriented graphs. In this thesis the author studies various properties of in-tournaments which relate to pancyclicity. In particular that of extendable cycles and pancyclic orderings. Among many other results, the thesis contains a sufficient condition in terms of the minimum indegree of the digraph for an in-tournament to be pancyclic, namely, it is shown that if \(D\) is a strong in-tournament on \(n\) vertices in which all indegrees are larger than \({n-1\over 3}\), then \(D\) is pancyclic.NEWLINENEWLINENEWLINEA digraph \(D= (V,A)\) on \(n\) vertices is a multipartite tournament (a semicomplete multipartite digraph) if it can be obtained from a tournament (a semicomplete digraph) \(D'= (V,A')\) by deleting all arcs \(x\to y\) for which \(x,y\in V_i\) for some \(i\) where we start from a fixed partition \(V= V_1\cup\cdots\cup V_k\), \(2\leq k\leq n\), of \(V\). Alternatively one can define semicomplete multipartite digraphs as those which one can obtain from a complete multipartite graph by replacing each edge \(xy\) by a directed arc \(x\to y\), or \(y\to x\) or the two arcs \(x\to y\), \(y\to x\). The author gives a characterization of those strongly connected semicomplete multipartite digraphs \(D\) that have two distinct vertices \(u_1\), \(u_2\) such that \(D- u_i\) is strong for \(i= 1,2\). The thesis also contains various sufficient conditions for a semicomplete multipartite digraph to be Hamiltonian.NEWLINENEWLINENEWLINEThe majority of the results in this thesis (from 1999) have now been published in research journals in graph theory.