The oriented diameter of graphs derived from other graphs
The diameter of a strong digraph or connected graph is the largest of the distances between its vertices. An orientation of an undirected graph \(G\) is a digraph obtained from \(G\) by assigning a direction to each edge. An orientation is said to be strong if the digraph is strongly connected. The oriented diameter of a graph \(G\) is the minimum diameter among all strong orientations of \(G\).\N\NIn this paper, the authors give bounds on the oriented diameter of two graphs derived from a given graph: the complement and the line graph. The authors give bounds on the oriented diameter of the complement of a graph \(G\) in terms of the diameter of \(G\) and in terms of the oriented diameter of \(G\). As a corollary, derive a Nordhaus-Gaddum-type result for the oriented diameter. The authors show that the oriented diameter of the line graph of a graph \(G\) cannot exceed the oriented diameter of \(G\) by more than 1, and that it is at least approximately the square root of the oriented diameter of \(G\). Finally, both results are proven to be the best possible in some sense.\N\NThe paper is well written and contains all the relevant previous results on the oriented diameter of graphs. It is an interesting contribution for those interested in metric graph theory.
- A complete characterisation of vertex-multiplications of trees with diameter 5
- A degree condition for diameter two orientability of graphs
- A Note on the Diameter of a Graph
- A survey of Nordhaus-Gaddum type relations
- A Theorem on Graphs, with an Application to a Problem of Traffic Control
- Almost minimum diameter orientations of semicomplete multipartite and extended digraphs
- An improvement to Chvátal and Thomassen's upper bound for oriented diameter
- Arc reversals of cycles in orientations of \(G\) vertex-multiplications
- AT-free graphs: Linear bounds for the oriented diameter
- Bilateral orientations and domination
- Complexity of approximating the oriented diameter of chordal graphs
- Diameter of orientations of graphs with given minimum degree
- Diameter three orientability of bipartite graphs
- Distances in orientations of graphs
- Ein Satz über Untermengen einer endlichen Menge.
- scientific article; zbMATH DE number 772778 (Why is no real title available?)
- scientific article; zbMATH DE number 3257169 (Why is no real title available?)
- Improved bound on the oriented diameter of graphs with given minimum degree
- Nordhaus-Gaddum-type theorem for diameter of graphs when decomposing into many parts
- On optimal orientation of cycle vertex multiplications
- On optimal orientations of \(G\) vertex-multiplications
- Optimal orientations of vertex-multiplications of Cartesian products of graphs
- Optimal orientations of Vertex-multiplications of Trees with Diameter 4
- Optimal oriented diameter of graphs with diameter 3
- Oriented diameter of graphs with diameter 3
- Oriented diameter of graphs with given maximum degree
- Oriented diameter of maximal outerplanar graphs
- Oriented diameter of star graphs
- The connectivity of line-graphs
- The Diameter of a Graph and its Complement
- The oriented diameter of graphs with given connected domination number and distance domination number
This page was built for publication: The oriented diameter of graphs derived from other graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7014495)
