✦ LIBER ✦

Kings in locally semicomplete digraphs

✍ Scribed by Ruixia Wang; Aimin Yang; Shiying Wang

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 94 KB
Volume: 63
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20426

No coin nor oath required. For personal study only.

✦ Synopsis

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‐king. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 279–287, 2010

📜 SIMILAR VOLUMES

Kings in semicomplete multipartite digra

Kings in semicomplete multipartite digraphs

✍ Gutin, Gregory; Yeo, Anders 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB

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

Weakly Hamiltonian-connected locally sem

Weakly Hamiltonian-connected locally semicomplete digraphs

✍ Bang-Jensen, J�rgen; Guo, Yubao; Volkmann, Lutz 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 630 KB

We characterize weakly hamiltonian-connected locally semicomplete digraphs.

Strongly Hamiltonian-connected locally s

Strongly Hamiltonian-connected locally semicomplete digraphs

✍ Guo, Yubao 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 513 KB

We give some sufficient conditions for locally semicomplete digraphs to contain a hamiltonian path from a prescribed vertex to another prescribed vertex. As an immediate consequence of these, we obtain that every 4-connected locally semicomplete digraph is strongly hamiltonian-connected. Our results

Locally semicomplete digraphs that are c

Locally semicomplete digraphs that are complementarym-pancyclic

✍ Guo, Yubao; Volkmann, Lutz 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 923 KB

If A and Bare two subdigraphs of D, then we denote by &(A, 5) the distance between A and 5. Let D be a 2-connected locally semicomplete digraph on n 2 6 vertices. If S is a minimum separating set of D and d = min{do-s(N+(s) -S, N-(s) -S ) l s E S}, then rn = max(3, d + 2) I n/2 and D contains t w o

Steiner type problems for digraphs that

Steiner type problems for digraphs that are locally semicomplete or extended semicomplete

✍ Jørgen Bang-Jensen; Gregory Gutin; Anders Yeo 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB

## Abstract We consider the following three problems: (P1) Let __D__ be a strong digraph and let __X__ be a non‐empty subset of its vertices. Find a strong subdigraph __D__′ of __D__ which contains all vertices of __X__ and has as few arcs as possible. This problem is also known under the name the

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