Characterization of vertex pancyclic and pancyclic ordinary complete multipartite digraphs
type: Item
instance of: scholarly article
title: Characterization of vertex pancyclic and pancyclic ordinary complete multipartite digraphs
zbMATH Open document ID: 0839.05042
DOI: 10.1016/0012-365X(93)E0195-A
author: G. Gutin
published in: Discrete Mathematics
publication date: 1996-06-18T00:00:00Z
review text: A digraph is semicomplete if it has no pair of non-adjacent vertices. A semicomplete multipartite digraph is a digraph that can be obtained from some semicomplete digraph \(D\) by choosing a (vertex) spanning collection of vertex disjoint induced subgraphs of \(D\) and deleting all arcs inside each of these. A semicomplete multipartite digraph is called ordinary if, whenever \(x\) and \(y\) are non-adjacent vertices they have exactly the same in- and out-neighbours. Such digraphs are also called extended semicomplete digraphs since the digraph obtained by shrinking each independent set of vertices to one vertex is a semicomplete digraph. Equivalently: every ordinary semicomplete multipartite digraph \(D\) can be obtained from some semicomplete digraph \(S\) by replacing each vertex \(x\) of \(S\) by an independent set of vertices \(I_x\) and adding all possible arcs from \(I_x\) to \(I_y\) if \(x\to y\) is an arc of \(S\). In this paper, the author gives a complete characterization of pancyclic and vertex pancyclic ordinary semicomplete multipartite digraphs. These characterizations which are non-trivial lead to polynomial algorithms. Note that the author uses the term complete multipartite digraph instead of semicomplete multipartite digraph. However the last term should be preferred (and is so today, I think) because the phrase complete digraph sometimes means a digraph in which each pair of vertices induces a 2-cycle. A digraph is quasi-transitive if whenever \(x\to y\) and \(y\to z\) are arcs where \(x\), \(y\), \(z\) are distinct there is an arc between \(x\) and \(z\) (note that the arc may go in any direction, or there could be one in each direction). In [the reviewer and \textit{J. Huang}, Quasi-transitive digraphs, J. Graph Theory 20, No. 2, 141-161 (1995; Zbl 0832.05048)] Gutin's characterizations of pancyclic and vertex pancyclic ordinary semicomplete multipartite digraphs were used to characterize pancyclic and vertex pancyclic quasi-transitive digraphs.…
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 778532
zbMATH Keywords: semicomplete multipartite digraph
zbMATH Keywords: extended semicomplete digraphs
zbMATH Keywords: independent set
zbMATH Keywords: characterization
zbMATH Keywords: polynomial algorithms
zbMATH Keywords: quasi-transitive digraphs
reviewed by: Jørgen Bang-Jensen
MaRDI profile type: Publication
cites work: Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
cites work: Cycles and paths of many lengths in bipartite digraphs
cites work: Weakly Hamiltonian-connected ordinary multipartite tournaments
cites work: Cycles in bipartite tournaments
cites work: Q4873829
cites work: Q3220618
cites work: Q3826582
cites work: On cycles in multipartite tournaments
cites work: Cycles and paths in bipartite tournaments with spanning configurations
cites work: Q5585195
cites work: Q4000792
cites work: Q3344011
full work available at URL: 0012-365x(93)e0195-a
OpenAlex ID: W2036118949
Recommended article: Q4031913
Recommended article: Vertex-pancyclism in the generalized sum of digraphs
Recommended article: Q5286396
Recommended article: Q3841332
Recommended article: A note on vertex pancyclic oriented graphs
Recommended article: Generalizing vertex pancyclic and \(k\)-ordered graphs
Recommended article: Notes on vertex pancyclicity of graphs
Recommended article: A characterization of pancyclic complements of line graphs
Recommended article: Vertex pancyclicity and new sufficient conditions
Recommended article: Vertex-pancyclicity of edge-face-total graphs
description: scientific article; zbMATH DE number 778532