Kings in Quasi-transitive digraphs

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstrakt

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. This definition generalizes the definition of a king in a tournament. We consider quasi-transitive digraphs - a generalization of tournaments recently investigated by the authors (Bang-Jensen and Huang, 1995). We prove that a quasi-transitive digraph has a 3-king if and only if it has an out-branching. We give several results on 3-kings in quasi-transitive digraphs which are analogous to well-known results about kings in tournaments.
OriginalsprogEngelsk
TidsskriftDiscrete Mathematics
Vol/bind185
Sider (fra-til)19-27
Antal sider9
ISSN0012-365X
DOI
StatusUdgivet - 1998

    Fingerprint

Citationsformater