The minimum diameter of orientations of complete multipartite graphs
A pair of integers \(\{p, q\}\) is called a co-pair if \(1\leq p\leq q\leq{p\choose \lfloor p/2\rfloor}\). A multiset \(\{p, q, r\}\) is a co-triple if both \(\{p, q\}\) and \(\{p, r\}\) are co-pairs. \(K(p_1,\dots,p_n)\) stands for complete \(n\)-partite graph with \(p_i\) vertices in the \(i\)th partite set. The authors prove that if \(\{p_1,\dots,p_n\}\) can be partitioned into co-pairs or into co-pairs and a co-triple, then there exists an orientation of \(K(p_1,\dots,p_n)\) of diameter two provided that \((n,p_1,p_2,p_3,p_4)\neq(4,1,1,1,1)\). This generalizes a result obtained by \textit{J. Plesník} [Acta Math. Univ. Comenianae 46/47, 225-236 (1985; Zbl 0613.05024)], \textit{G. Gutin} [Graphs Comb. 10, No. 3, 225-230 (1994; Zbl 0814.05044)], and the authors [Discrete Math. 149, No. 1-3, 131-139 (1996; Zbl 0846.05038)].
- The diameter of an orientation of a complete multipartite graph
- Diameter of orientations of graphs with given minimum degree
- Almost minimum diameter orientations of semicomplete multipartite and extended digraphs
- Minimizing and maximizing the diameter in orientations of graphs
- Minimum diameter orientations for tree vertex-multiplication graphs
- scientific article; zbMATH DE number 3991541
- scientific article; zbMATH DE number 3991530
- Improved bound on the oriented diameter of graphs with given minimum degree
- Strong orientations of complete k-partite graphs achieving the strong diameter
- Oriented diameter of graphs with given maximum degree
- A Theorem on Graphs, with an Application to a Problem of Traffic Control
- Distances in orientations of graphs
- Every vertex a king
- scientific article; zbMATH DE number 3991541 (Why is no real title available?)
- Minimizing and maximizing the diameter in orientations of graphs
- Robbins's Theorem for Mixed Multigraphs
- The diameter of an orientation of a complete multipartite graph
- On a conjecture concerning the orientation number of a graph
- Addendum to: The diameter of an orientation of a complete multipartite graph [Discrete Math. 149 (1996) 131--139]
- Optimal orientations of products of paths and cycles
- On optimal orientations of Cartesian products of graphs. I
- A degree condition for diameter two orientability of graphs
- Minimum average distance of strong orientations of graphs
- The diameter of an orientation of a complete multipartite graph
- On optimal orientations of Cartesian products with a bipartite graph
- Diameters of cocircuit graphs of oriented matroids: an update
- Diameter of orientations of graphs with given minimum degree
- On optimal orientation of cycle vertex multiplications
- A size condition for diameter two orientable graphs
- scientific article; zbMATH DE number 6672459 (Why is no real title available?)
- scientific article; zbMATH DE number 5976594 (Why is no real title available?)
- scientific article; zbMATH DE number 4204370 (Why is no real title available?)
- scientific article; zbMATH DE number 5307866 (Why is no real title available?)
- On optimal orientations of complete tripartite graphs
- The orientation number of two complete graphs with linkages
- Minimum and maximum strong diameters of the Cartesian and strong products of cycles
- Oriented diameter of graphs with diameter 3
This page was built for publication: The minimum diameter of orientations of complete multipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2563422)
