Diameter three orientability of bipartite graphs
type: Item
instance of: scholarly article
title: Diameter three orientability of bipartite graphs
zbMATH Open document ID: 1465.05030
DOI: 10.37236/9723
author: Bin Chen
author: An Chang
published in: The Electronic Journal of Combinatorics
publication date: 2021-06-07T00:00:00Z
review text: Summary: In [Discrete Math. 342, No. 4, 1063--1065 (2019; Zbl 1405.05044)], \textit{É. Czabarka} et al. showed that for every undirected graph of order \(n\), the minimum degree threshold for diameter two orientability is \(\frac{n}{2}+ \Theta(\ln n)\). In this paper, we consider bipartite graphs and give a sufficient condition in terms of the minimum degree for such graphs to have oriented diameter three. We in particular prove that for balanced bipartite graphs of order \(n\), the minimum degree threshold for diameter three orientability is \(\frac{n}{4}+\Theta(\ln n)\).
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 7356168
zbMATH Keywords: distance
zbMATH Keywords: diameter
zbMATH Keywords: orientation
zbMATH Keywords: oriented diameter
zbMATH Keywords: minimum degree
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.37236/9723
OpenAlex ID: W3163988689
cites work: Digraphs
cites work: Diameter of orientations of graphs with given minimum degree
cites work: Robbins's Theorem for Mixed Multigraphs
cites work: Distances in orientations of graphs
cites work: A size condition for diameter two orientable graphs
cites work: A degree condition for diameter two orientability of graphs
cites work: Oriented diameter of graphs with given maximum degree
cites work: AT-free graphs: Linear bounds for the oriented diameter
cites work: Q3353039
cites work: Optimal orientations of graphs and digraphs: A survey
cites work: Bounds for the minimum oriented diameter
cites work: Oriented diameter of graphs with diameter 3
cites work: Diametrically critical tournaments
cites work: A Theorem on Graphs, with an Application to a Problem of Traffic Control
cites work: A Remark on Stirling's Formula
cites work: Q3754023
cites work: Improved bound on the oriented diameter of graphs with given minimum degree
description: scientific article; zbMATH DE number 7356168