On optimal orientations of complete tripartite graphs

zbMATH Open1468.05101arXiv2001.01908MaRDI QIDQ5000286FDOQ5000286

Willie Han Wah Wong, E. G. Tay

Publication date: 12 July 2021

Abstract: Given a connected and bridgeless graph $G$, let $mathscrD(G)$ be the family of strong orientations of $G$. The orientation number of $G$ is defined to be $$, where $d(D)$ is the diameter of the digraph $D$. In this paper, we focus on the orientation number of complete tripartite graphs. We prove a conjecture raised by Rajasekaran and Sampathkumar. Specifically, for $qgepge3$, if $$, then $qlepchooselfloorp/2floor$. We also present some sufficient conditions on $p$ and $q$ for $$.

Full work available at URL: https://arxiv.org/abs/2001.01908

zbMATH Keywords

bridgeless graphorientation number

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Distances in orientations of graphs
• Optimal orientations of graphs and digraphs: A survey
• Robbins's Theorem for Mixed Multigraphs
• Minimizing and maximizing the diameter in orientations of graphs
• Optimal orientations of some complete tripartite graphs
• The diameter of an orientation of a complete multipartite graph
• The minimum diameter of orientations of complete multipartite graphs
• Diametrically critical tournaments

Cited In (2)

• On imbalances in oriented tripartite graphs
• Title not available (Why is that?)

Uses Software

• Maple

This page was built for publication: On optimal orientations of complete tripartite graphs

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