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 Kr(T) denote the set of r-kings of T. Let Q be the subdigraph of T induced by K4(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 K4(Q)K4(T), Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249–258] showed that K3(Q)K3(T) and K2(Q)=K2(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 K3(Q) need not be the same as K3(T) in general and posed the problem: characterize all those semicomplete multipartite digraphs T such that K3(Q)=K3(T). In the course of proving our result (1), we (2) show that K3(Q)=K3(T) for all semicomplete multipartite digraphs T with no transmitters such that Q is a semicomplete digraph.