Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs
type: Item
instance of: scholarly article
title: Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs
zbMATH Open document ID: 0962.05032
DOI: 10.1016/S0012-365X(00)00055-8
author: G. Gutin
author: Meike Tewes
author: A. Yeo
published in: Discrete Mathematics
publication date: 2001-06-04T00:00:00Z
review text: A digraph obtained by replacing each edge of a complete multipartite graph by an arc or a pair of mutually opposite arcs is called a semicomplete digraph. An oriented graph is a digraph with no directed cycle of length two. In [Ars Comb. 58, 271-278 (2001)], the reviewer raised the following question: Let \(D\) be a strong semicomplete multipartite digraph with a longest directed path of length \(p\). Does there exist a strong spanning oriented subgraph with a longest directed path of length \(p\)? The authors present the following complete answer to this question. Every strong semicomplete multipartite digraph \(D\) with a longest directed path of length \(p\), which is not bipartite with a partite set of cardinality one, has a strong spanning oriented subgraph with a longest directed path of length at least \(p-2\). Examples show that the bound \(p-2\) is best possible.
reviewed by: Lutz Volkmann
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1506835
zbMATH Keywords: semicomplete multipartite digraph
zbMATH Keywords: spanning subgraph
zbMATH Keywords: path
MaRDI profile type: Publication
full work available at URL: s0012-365x(00)00055-8
OpenAlex ID: W1964296470
Recommended article: Longest paths in semicomplete multipartite digraphs
Recommended article: Longest paths through an arc in strong semicomplete multipartite digraphs
Recommended article: Q3767374
Recommended article: Longest paths and cycles in bipartite oriented graphs
Recommended article: Q3722538
Recommended article: Finding a Longest Path in a Complete Multipartite Digraph
Recommended article: The ratio of the longest cycle and longest path in semicomplete multipartite digraphs
Recommended article: The minimum spanning strong subdigraph problem for extended semicomplete digraphs and semicomplete bipartite digraphs
Recommended article: Q3768926
Recommended article: Q4568152
description: scientific article; zbMATH DE number 1506835