The structure of strong arc-locally in-semicomplete digraphs
type: Item
instance of: scholarly article
title: The structure of strong arc-locally in-semicomplete digraphs
zbMATH Open document ID: 1183.05032
author: Ruixia Wang
author: Shiying Wang
published in: Discrete Mathematics
publication date: 2009-12-15T00:00:00Z
review text: The main result in [\textit{J. Bang-Jensen}, ``The structure of strong arc-locally semicomplete digraphs,'' Discrete Math. 283, No. 1--3, 1--6 (2004; Zbl 1048.05038)] is that a strong arc-locally semicomplete digraph is either semicomplete, semicomplete bipartite or an extended cycle. The authors show that in this classification a class of digraphs that they call \(W_n\) must be included. The goal of the paper is to obtain an analogous result for strong arc-locally in-semicomplete digraphs. It is shown that a strong arc-locally in-semicomplete digraph is either semicomplete, semicomplete bipartite, an extended cycle or a \(T\)-digraph. Roughly speaking, a \(T\)-digraph is defined as a digraph formed by four pieces (two digraphs with no arcs, a trivial digraph, and a semicomplete digraph) and some adjacencies between these pieces. The result is used to show that a conjecture of Bang-Jensen is true (Conjecture 4.3 in the above mentioned reference).
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 5648216
zbMATH Keywords: digraphs
zbMATH Keywords: arc-locally in-semicomplete digraph
zbMATH Keywords: arc-locally semicomplete digraph
zbMATH Keywords: semicomplete digraph
zbMATH Keywords: semicomplete bipartite digraph
reviewed by: Josep M. Brunat
MaRDI profile type: Publication
full work available at URL: j.disc.2009.06.033
OpenAlex ID: W2017430327
cites work: Locally semicomplete digraphs: A generalization of tournaments
cites work: Paths and cycles in extended and decomposable digraphs
cites work: A classification of locally semicomplete digraphs
cites work: The structure of strong arc-locally semicomplete digraphs
cites work: Kernels and perfectness in arc-local tournament digraphs
cites work: Independent sets and non-augmentable paths in generalizations of tournaments
cites work: Path-connectivity in local tournaments
DOI: 10.1016/J.DISC.2009.06.033
Recommended article: The structure of strong arc-locally semicomplete digraphs
Recommended article: Q4326185
Recommended article: A classification of arc-locally semicomplete digraphs
Recommended article: A classification of all arc-locally semicomplete digraphs
Recommended article: On the structure of locally semicomplete digraphs
Recommended article: On minimum locally $n$-(arc)-strong digraphs
Recommended article: Local strongly arc-connectivity in regular bipartite digraphs
Recommended article: Q4874600
Recommended article: Locally Semicomplete Digraphs and Generalizations
Recommended article: Arc‐disjoint strong spanning subdigraphs of semicomplete compositions
description: scientific article; zbMATH DE number 5648216