Please use this identifier to cite or link to this item:
|Title:||On semicomplete multipartite digraphs whose king sets are semicomplete digraphs|
Semicomplete multipartite digraphs
|Citation:||Tan, B.P. (2008-06-28). On semicomplete multipartite digraphs whose king sets are semicomplete digraphs. Discrete Mathematics 308 (12) : 2564-2570. ScholarBank@NUS Repository. https://doi.org/10.1016/j.disc.2007.06.002|
|Abstract:||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. © 2007 Elsevier B.V. All rights reserved.|
|Source Title:||Discrete Mathematics|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on May 20, 2018
checked on May 18, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.