Almost minimum diameter orientations of semicomplete multipartite and extended digraphs

DOI10.1007/S003730200036MaRDI QIDQ1865138zbMATH OpenOpenAlexFDO

Authors G. Gutin, E. G. Tay, A. Yeo, K. M. Koh

Publication date 25 March 2003

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s003730200036

zbMATH Keywords

diameterdigraphorientation

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20)

Review text

A digraph \(D\) is semicomplete if there is at least one arc between any pair of distinct vertices of \(D\). The \((s_1, s_2, \dots , s_n)\)-extension \(D(s_1, s_2, \dots , s_n)\) of a digraph \(D\) with vertices labelled \(1,2,\dots , n\) is obtained from \(D\) by replacing every vertex \(i\) by a set of \(s_i\) independent vertices. An orientation of a digraph \(D\) is a digraph obtained from \(D\) by deleting exactly one arc between \(x\) and \(y\) for every pair \(x\neq y\) of vertices such that both \(xy\) and \(yx\) are in \(D\). Almost minimum diameter orientations of certain semicomplete multipartite and extended digraphs are considered. Several generalizations of known results are proved. A survey of previous results can be found in the book of \textit{J. Bang-Jensen} and \textit{G. Gutin} [Digraphs. Theory, algorithms and applications (Springer Monographs in Mathematics, Springer, London) (2001; Zbl 0958.05002)].

Recommendations

• Orientations of digraphs almost preserving diameter
• Locally semicomplete digraphs: A generalization of tournaments
• Semicomplete Multipartite Digraphs
• Spanning multipartite tournaments of semicomplete multipartite digraphs.
• The diameter of an orientation of a complete multipartite graph

Cited in

(11)

• Orientations of digraphs almost preserving diameter
• Diameter of orientations of graphs with given minimum degree
• Multipartite tournaments: a survey
• The minimum diameter of orientations of complete multipartite graphs
• Semicomplete Multipartite Digraphs
• scientific article; zbMATH DE number 5307866 (Why is no real title available?)
• Optimal orientations of vertex-multiplications of Cartesian products of graphs
• Large girth and small oriented diameter graphs
• Diameter of orientations of graphs with given order and number of blocks
• The oriented diameter of graphs derived from other graphs
• On the oriented diameter of near planar triangulations

This page was built for publication: Almost minimum diameter orientations of semicomplete multipartite and extended digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1865138)