Diameter three orientability of bipartite graphs

DOI10.37236/9723MaRDI QIDQ2030744zbMATH OpenOpenAlexFDO

Authors Bin Chen, An Chang

Publication date 7 June 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/9723

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

diameterdistanceminimum degreeorientationoriented diameter

Mathematics Subject Classification ID

Vertex degrees (05C07) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35)

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)\).

Recommendations

• A degree condition for diameter two orientability of graphs
• Oriented diameter of graphs with given maximum degree
• A size condition for diameter two orientable graphs
• Diameter of orientations of graphs with given minimum degree
• Improved bound on the oriented diameter of graphs with given minimum degree

Cites work

• A degree condition for diameter two orientability of graphs
• A Remark on Stirling's Formula
• A size condition for diameter two orientable graphs
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• AT-free graphs: Linear bounds for the oriented diameter
• Bounds for the minimum oriented diameter
• Diameter of orientations of graphs with given minimum degree
• Diametrically critical tournaments
• Digraphs
• Distances in orientations of graphs
• scientific article; zbMATH DE number 4204370 (Why is no real title available?)
• scientific article; zbMATH DE number 3991541 (Why is no real title available?)
• Improved bound on the oriented diameter of graphs with given minimum degree
• Optimal orientations of graphs and digraphs: A survey
• Oriented diameter of graphs with diameter 3
• Oriented diameter of graphs with given maximum degree
• Robbins's Theorem for Mixed Multigraphs

Cited in

(11)

• On large bipartite graphs of diameter 3
• DDR Graphs of Diameter Three
• Oriented diameter of graphs with given maximum degree
• The oriented diameter of graphs with given connected domination number and distance domination number
• Large girth and small oriented diameter graphs
• Diameter two orientability of mixed graphs
• Diameter three orientability of mixed bipartite graphs
• The oriented diameter of graphs derived from other graphs
• On the oriented diameter of near planar triangulations
• The oriented diameter of mixed multigraphs with diameter 2
• Oriented diameter of graphs with diameter 3

This page was built for publication: Diameter three orientability of bipartite graphs

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