Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.disc.2007.06.002
Title: On semicomplete multipartite digraphs whose king sets are semicomplete digraphs
Authors: Tan, B.P. 
Keywords: Distances
Kings
Multipartite tournaments
Semicomplete multipartite digraphs
Issue Date: 28-Jun-2008
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
URI: http://scholarbank.nus.edu.sg/handle/10635/103753
ISSN: 0012365X
DOI: 10.1016/j.disc.2007.06.002
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

1
checked on Nov 13, 2018

Page view(s)

64
checked on Oct 26, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.