A degree condition for diameter two orientability of graphs

DOI10.1016/J.DISC.2018.12.012MaRDI QIDQ1727780zbMATH OpenOpenAlexWikidataFDO

Authors Éva Czabarka, Peter Dankelmann, László A. Székely

Publication date 20 February 2019

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

distanceminimum degreediameterorientationoriented diameter

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Distance in graphs (05C12)

Abstract: For $ninmathbbN$ let $delt{a}_n$ be the smallest value such that every graph of order $n$ and minimum degree at least $delt{a}_n$ admits an orientation of diameter two. We show that $delt{a}_n=fracn2+Theta(lnn)$.

Recommendations

• A size condition for diameter two orientable graphs
• Diameter of orientations of graphs with given minimum degree
• scientific article; zbMATH DE number 4059432
• Oriented diameter of graphs with given maximum degree
• Oriented diameter of graphs with given girth and maximum degree
• The diameter of an orientation of a complete multipartite graph
• scientific article; zbMATH DE number 3991530
• On fully orientability of 2-degenerate graphs
• Orientation of 2-edge-connected graphs with diameter 3
• Planar oriented graphs of diameter two

Cites work

• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• A size condition for diameter two orientable graphs
• AT-free graphs: Linear bounds for the oriented diameter
• Bounds for the minimum oriented diameter
• Complexity of approximating the oriented diameter of chordal graphs
• Diameter of orientations of graphs with given minimum degree
• Distances in orientations of graphs
• Improved bound on the oriented diameter of graphs with given minimum degree
• Minimizing the oriented diameter of a planar graph
• On optimal orientations of Cartesian products of trees
• On optimal orientations of Cartesian products with a bipartite graph
• Optimal orientations of graphs and digraphs: A survey
• Orientation of 2-edge-connected graphs with diameter 3
• Orientations of digraphs almost preserving diameter
• Oriented diameter of graphs with diameter 3
• Oriented diameter of graphs with given maximum degree
• The diameter of an orientation of a complete multipartite graph
• The minimum diameter of orientations of complete multipartite graphs

Cited in

(13)

• Oriented diameter of maximal outerplanar graphs
• Orientations of graphs and minimum degrees of graphs.
• Separating systems and oriented graphs of diameter two
• The oriented diameter of graphs with given connected domination number and distance domination number
• Diameter three orientability of bipartite graphs
• scientific article; zbMATH DE number 2192196 (Why is no real title available?)
• On fully orientability of 2-degenerate graphs
• Improved bound on the oriented diameter of graphs with given minimum degree
• Large girth and small oriented diameter graphs
• A size condition for diameter two orientable graphs
• Oriented diameter of graphs with given maximum degree
• scientific article; zbMATH DE number 4059432 (Why is no real title available?)
• Diameter of orientations of graphs with given minimum degree

This page was built for publication: A degree condition for diameter two orientability of graphs

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