## Abstract

Let G be a bridgeless graph. An orientation of G is a digraph obtained from G by assigning a direction to each edge. The oriented diameter of G is the minimum diameter among all strong orientations of G. The connected domination number γ_{c}(G) of G is the minimum cardinality of a set S of vertices of G such that every vertex of G is in S or adjacent to some vertex of S, and which induces a connected subgraph in G. We prove that the oriented diameter of a bridgeless graph G is at most 2 γ_{c}(G) + 3 if γ_{c}(G) is even and 2 γ_{c}(G) + 2 if γ_{c}(G) is odd. This bound is sharp. For d∈ N , the d-distance domination number γ^{d}(G) of G is the minimum cardinality of a set S of vertices of G such that every vertex of G is at distance at most d from some vertex of S. As an application of a generalisation of the above result on the connected domination number, we prove an upper bound on the oriented diameter of the form (2 d+ 1) (d+ 1) γ^{d}(G) + O(d) . Furthermore, we construct bridgeless graphs whose oriented diameter is at least (d+ 1) ^{2}γ^{d}(G) + O(d) , thus demonstrating that our above bound is best possible apart from a factor of about 2.

Original language | English |
---|---|

Article number | 18 |

Journal | Graphs and Combinatorics |

Volume | 40 |

Issue number | 1 |

DOIs | |

Publication status | Published - Feb 2024 |

## Keywords

- Connected domination
- Diameter
- Distance domination
- Domination
- Orientation number
- Oriented diameter

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics