On semicomplete multipartite digraphs whose king sets are semicomplete digraphs

Reid [Every vertex a king, Discrete Math. 38 (1982) 93-98] showed that a non-trivial tournament H is contained in a tournament whose 2-kings are exactly the vertices of H if and only if H contains no transmitter. Let T be a semicomplete multipartite digraph with no transmitters and let K_r(T) denote the set of r-kings of T. Let Q be the subdigraph of T induced by K₄(T). Very recently, Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] proved that Q contains no transmitters and gave an example to show that the direct extension of Reid's result to semicomplete multipartite digraphs with 2-kings replaced by 4-kings is not true. In this paper, we (1) characterize all semicomplete digraphs D which are contained in a semicomplete multipartite digraph whose 4-kings are exactly the vertices of D. While it is trivial that K₄(Q)⊆K₄(T), Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] showed that K₃(Q)⊆K₃(T) and K₂(Q)=K₂(T). Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] also provided an example to show that K₃(Q) need not be the same as K₃(T) in general and posed the problem: characterize all those semicomplete multipartite digraphs T such that K₃(Q)=K₃(T). In the course of proving our result (1), we (2) show that K₃(Q)=K₃(T) for all semicomplete multipartite digraphs T with no transmitters such that Q is a semicomplete digraph.     

Kings in semicomplete multipartite digraphs

A digraph obtained by replacing each edge of a complete p‐partite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a semicomplete p‐partite digraph, or just a semicomplete multipartite digraph. A semicomplete multipartite digraph with no cycle of length two is a multipartite tournament. In a digraph D, an r‐king is a vertex q such that every vertex in D can be reached from q by a path of length at most r. Strengthening a theorem by K. M. Koh and B. P. Tan (Discr Math 147 (1995), 171–183) on the number of 4‐kings in multipartite tournaments, we characterize semicomplete multipartite digraphs, which have exactly k 4‐kings for every k = 1, 2, 3, 4, 5. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 177‐183, 2000     

Strongly quasi-Hamiltonian-connected semicomplete multipartite digraphs

A semicomplete multipartite or semicomplete c$c$-partite digraph D$D$ is a biorientation of a c$c$-partite graph. A semicomplete multipartite digraph D$D$ is called strongly quasi-Hamiltonian-connected, if for any two distinct vertices x$x$ and y$y$ of D$D$, there is a path P$P$ from x$x$ to y$y$ such that P$P$ contains at least one vertex from each partite set of D$D$.     

Minimum cost homomorphisms to semicomplete multipartite digraphs

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism ofDtoH if uv∈A(D) implies f(u)f(v)∈A(H). For a fixed directed or undirected graph H and an input graph D, the problem of verifying whether there exists a homomorphism of D to H has been studied in a large number of papers. We study an optimization version of this decision problem. Our optimization problem is motivated by a real-world problem in defence logistics and was introduced recently by the authors and M. Tso.Suppose we are given a pair of digraphs D,H and a cost c_i(u) for each u∈V(D) and i∈V(H). The cost of a homomorphism f of D to H is ∑_u∈V(D)c_f(u)(u). Let H be a fixed digraph. The minimum cost homomorphism problem for H, MinHOMP(H), is stated as follows: For input digraph D and costs c_i(u) for each u∈V(D) and i∈V(H), verify whether there is a homomorphism of D to H and, if it does exist, find such a homomorphism of minimum cost. In our previous paper we obtained a dichotomy classification of the time complexity of when H is a semicomplete digraph. In this paper we extend the classification to semicomplete k-partite digraphs, k≥3, and obtain such a classification for bipartite tournaments.     

A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs

We describe a polynomial algorithm for the Hamiltonian cycle problem for semicomplete multipartite digraphs. The existence of such an algorithm was conjectured in G. Gutin, Paths and cycles in digraphs. Ph. D. thesis, Tel Aviv Univ., 1993. (see also G. Gutin, J Graph Theory 19 (1995) 481–505). © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 111–132, 1998     

Cycles and paths in semicomplete multipartite digraphs,theorems, and algorithms: a survey

A digraph obtained by replacing each edge of a complete m-partite graph by an arc or a pair of mutually opposite arcs with the same end vertices is calied a semicomplete m-partite digraph. We describe results (theorems and algorithms) on directed walks in semicomplete m-partite digraphs, including some recent results concerning tournaments. © 1995 John Wiley & Sons, Inc.     

Kings in locally semicomplete digraphs

A k‐king in a digraph D is a vertex which can reach every other vertex by a directed path of length at most k. We consider k‐kings in locally semicomplete digraphs and mainly prove that all strong locally semicomplete digraphs which are not round decomposable contain a 2‐king. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 279–287, 2010     

Strongly Hamiltonian-connected locally semicomplete digraphs

We give some sufficient conditions for locally semicomplete digraphs to contain a hamiltonian path from a prescribed vertex to another prescribed vertex. As an immediate consequence of these, we obtain that every 4-connected locally semicomplete digraph is strongly hamiltonian-connected. Our results extend those of Thomassen [12] for tournaments. © 1996 John Wiley & Sons, Inc.     

Weakly Hamiltonian-connected locally semicomplete digraphs

We characterize weakly hamiltonian-connected locally semicomplete digraphs. Our result extends those of Thomassen. (J. Combinatorial Theory B 28 (1980), 142–163) for tournaments. © 1996 John Wiley & Sons, Inc.     

Connectivity properties of locally semicomplete digraphs

It is shown that every k-connected locally semicomplete digraph D with minimum outdegree at least 2k and minimum indegree at least 2k ? 2 has at least m = max{2, k} vertices x₁, x₂, ?, x_m such that D ? x_i is k-connected for i = 1, 2, ?, m.     

On the structure of locally semicomplete digraphs

In this paper we continue the study, started by J. Bang-Jensen (1989), of locally semicomplete digraphs, a generalization of tournaments, to which many well-known tournament results extend. The underlying undirected graphs of the locally semicomplete digraphs are precisely the proper circular-arc graphs. We give new results on the structure of locally semicomplete digraphs, as well as several examples of properties of tournaments and semicomplete digraphs that do not extend to the class of locally semicomplete digraphs.     

A classification of all arc-locally semicomplete digraphs

Arc-locally semicomplete digraphs were introduced by Bang-Jensen as a common generalization of both semicomplete and semicomplete bipartite digraphs in 1993. Later, Bang-Jensen (2004), Galeana-Sánchez and Goldfeder (2009) and Wang and Wang (2009) provided a characterization of strong arc-locally semicomplete digraphs. In this paper, we provide a characterization of strong and non-strong arc-locally semicomplete digraphs which generalizes some results by Bang-Jensen.     

Locally semicomplete digraphs that are complementary m-pancyclic

If A and B are two subdigraphs of D, then we denote by d_D (A, B) the distance between A and B. Let D be a 2-connected locally semicomplete digraph on n ≥ 6 vertices. If S is a minimum separating set of D and then m = max{3, d + 2} ≤ n/2 and D contains two vertex-disjoint dicycles of lengths t and n − t for every integer t satisfying m ≤ t ≤ n/2, unless D is a member of a family of locally semicomplete digraphs. This result extends those of Reid (Ann. Discrete Math. 27 (1985), 321–334) and Song (J. Combin. Theory B 57 (1993), 18–25) for tournaments, and it confirms two conjectures of Bang-Jensen (Discrete Math. 100 (1992), 243–265. © 1996 John Wiley & Sons, Inc.     

Minimum cost and list homomorphisms to semicomplete digraphs

For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism of D to H if uv∈A(D) implies f(u)f(v)∈A(H). Let H be a fixed directed or undirected graph. The homomorphism problem for H asks whether a directed or undirected input graph D admits a homomorphism to H. The list homomorphism problem for H is a generalization of the homomorphism problem for H, where every vertex x∈V(D) is assigned a set L_x of possible colors (vertices of H).The following optimization version of these decision problems generalizes the list homomorphism problem and was introduced in Gutin et al. [Level of repair analysis and minimum cost homomorphisms of graphs, Discrete Appl. Math., to appear], where it was motivated by a real-world problem in defence logistics. Suppose we are given a pair of digraphs D,H and a positive integral cost c_i(u) for each u∈V(D) and i∈V(H). The cost of a homomorphism f of D to H is . For a fixed digraph H, the minimum cost homomorphism problem for H is stated as follows: for an input digraph D and costs c_i(u) for each u∈V(D) and i∈V(H), verify whether there is a homomorphism of D to H and, if one exists, find such a homomorphism of minimum cost.We obtain dichotomy classifications of the computational complexity of the list homomorphism and minimum cost homomorphism problems, when H is a semicomplete digraph (digraph in which there is at least one arc between any two vertices). Our dichotomy for the list homomorphism problem coincides with the one obtained by Bang-Jensen, Hell and MacGillivray in 1988 for the homomorphism problem when H is a semicomplete digraph: both problems are polynomial solvable if H has at most one cycle; otherwise, both problems are NP-complete. The dichotomy for the minimum cost homomorphism problem is different: the problem is polynomial time solvable if H is acyclic or H is a cycle of length 2 or 3; otherwise, the problem is NP-hard.     

The complexity of colouring by locally semicomplete digraphs

In this paper we establish a dichotomy theorem for the complexity of homomorphisms to fixed locally semicomplete digraphs. It is also shown that the same dichotomy holds for list homomorphisms. The polynomial algorithms follow from a different, shorter proof of a result by Gutjahr, Welzl and Woeginger.     

Spanning 2-strong tournaments in 3-strong semicomplete digraphs

We prove that every 3-strong semicomplete digraph on at least 5 vertices contains a spanning 2-strong tournament. Our proof is constructive and implies a polynomial algorithm for finding a spanning 2-strong tournament in a given 3-strong semicomplete digraph. We also show that there are infinitely many (2k−2)-strong semicomplete digraphs which contain no spanning k-strong tournament and conjecture that every(2k−1)-strong semicomplete digraph which is not the complete digraph on 2k vertices contains a spanning k-strong tournament.