𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Kings in semicomplete multipartite digraphs

✍ Scribed by Gutin, Gregory; Yeo, Anders

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
92 KB
Volume
33
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

One-diregular subgraphs in semicomplete
One-diregular subgraphs in semicomplete multipartite digraphs
✍ Yeo, Anders πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 154 KB

The problem of finding necessary and sufficient conditions for a semicomplete multipartite digraph (SMD) to be Hamiltonian, seems to be both very interesting and difficult. Bang-Jensen, Gutin and Huang (Discrete Math to appear) proved a sufficient condition for a SMD to be Hamiltonian. A strengtheni

Kings in locally semicomplete digraphs
Kings in locally semicomplete digraphs
✍ Ruixia Wang; Aimin Yang; Shiying Wang πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 94 KB

## Abstract 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