Kings in Quasi-transitive digraphs

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review


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.
TidsskriftDiscrete Mathematics
Sider (fra-til)19-27
Antal sider9
StatusUdgivet - 1998

Fingeraftryk Dyk ned i forskningsemnerne om 'Kings in Quasi-transitive digraphs'. Sammen danner de et unikt fingeraftryk.