Orientations of digraphs almost preserving diameter
type: Item
instance of: scholarly article
title: Orientations of digraphs almost preserving diameter
zbMATH Open document ID: 1003.05049
DOI: 10.1016/S0166-218X(01)00298-0
author: G. Gutin
author: A. Yeo
published in: Discrete Applied Mathematics
publication date: 2002-08-29T00:00:00Z
review text: An orientation of a digraph \(D\) is an oriented graph \(H\) obtained by removing exactly one arc of each 2-cycle of \(D\). The authors prove that if \(D\) belongs to certain classes \(C\) of digraphs, then there exists an orientation \(H\) of \(D\) such that \(\text{diam}(H)\leq \max\{c,\text{diam}(D)\}\) where \(c\) is a constant whose value depends on the class \(C\). For example, if \(C\) is the class of strong semicomplete bipartite digraphs with at least two nodes in each partite set, then \(c=5\).
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 1792338
zbMATH Keywords: digraphs
zbMATH Keywords: diameter
reviewed by: J. W. Moon
MaRDI profile type: Publication
cites work: A classification of locally semicomplete digraphs
cites work: Generalizations of tournaments: A survey
cites work: A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs
cites work: Quasi‐transitive digraphs
cites work: Robbins's Theorem for Mixed Multigraphs
cites work: Strongly connected orientations of mixed multigraphs
cites work: Distances in orientations of graphs
cites work: Methods and problems of communication in usual networks
cites work: A survey of gossiping and broadcasting in communication networks
cites work: Spanning multipartite tournaments of semicomplete multipartite digraphs.
full work available at URL: s0166-218x(01)00298-0
OpenAlex ID: W1984850030
Recommended article: Q3754020
Recommended article: Diameter of orientations of graphs with given minimum degree
Recommended article: Almost minimum diameter orientations of semicomplete multipartite and extended digraphs
Recommended article: The diameter of an orientation of a complete multipartite graph
Recommended article: Q3794201
Recommended article: Minimizing and maximizing the diameter in orientations of graphs
Recommended article: Q3754023
Recommended article: Oriented diameter of graphs with given maximum degree
Recommended article: On unavoidable digraphs in orientations of graphs
Recommended article: On the dimension of oriented graphs
description: scientific article; zbMATH DE number 1792338