Longest paths in semicomplete multipartite digraphs
type: Item
instance of: scholarly article
title: Longest paths in semicomplete multipartite digraphs
zbMATH Open document ID: 0928.05036
DOI: 10.1016/S0012-365X(98)00301-X
author: Lutz Volkmann
published in: Discrete Mathematics
publication date: 1999-08-09T00: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 multipartite digraph. The author studies some properties of longest paths in semicomplete multipartite digraphs. He characterizes semicomplete \(n\)-partite digraphs whose longest path is of order \(n\), and states the problem to characterize semicomplete \(n\)-particle digraphs whose longest cycle is of order \(n\).
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1321815
zbMATH Keywords: semicomplete multipartite digraph
zbMATH Keywords: longest paths
zbMATH Keywords: longest cycle
reviewed by: G. Gutin
MaRDI profile type: Publication
full work available at URL: s0012-365x(98)00301-x
OpenAlex ID: W2068894802
Recommended article: Longest paths through an arc in strong semicomplete multipartite digraphs
Recommended article: Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs
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: On the longest path in a recursively partitionable graph
Recommended article: Q3767374
Recommended article: Longest paths and cycles in bipartite oriented graphs
Recommended article: Q3199444
Recommended article: Q4374378
Recommended article: Longest paths and longest cycles in graphs with large degree sums
description: scientific article; zbMATH DE number 1321815