Oriented Diameter of Mixed Graphs with Given Maximum Undirected Degree

Abstract

In 2018, Dankelmann, Gao, and Surmacs [J. Graph Theory, 88(1): 5--17, 2018] established sharp bounds on the oriented diameter of a bridgeless undirected graph and a bridgeless undirected bipartite graph in terms of vertex degree. In this paper, we extend these results to \emph{mixed graphs}, which contain both directed and undirected edges. Let the \emph{undirected degree} $d_G^{\ast }(x)$ of a vertex $x\in V(G)$ be the number of its incident undirected edges in a mixed graph $G$ of order $n$, and let the \emph{maximum undirected degree} be $\hat{I}{”}^{\ast }(G)=\max \{d_G^{\ast }(v):v\in V(G)\}$. We prove that \begin{align*} \text{(1)}\quad & \overrightarrow{\mathrm{diam}}(G) \leq n - Δ^* + 3 && \text{if $G$ is undirected, or contains a vertex $u$ with $d_G^{\ast }(u)=\hat{I}{”}^{\ast }$} \\ & && \text{and $d_G^{+}(u)+d_G^{-}(u)\ge 2$, or $\hat{I}{”}^{\ast }=5$ and $d_G^{+}(u)+d_G^{-}(u)=1$;} \\ \text{(2)}\quad & \overrightarrow{\mathrm{diam}}(G) \leq n - Δ^* + 4 && \text{otherwise}. \end{align*} We also establish bounds for mixed bipartite graphs. If $G$ is a bridgeless mixed bipartite graph with partite sets $A$ and $B$, and $u\in B$, then \begin{align*} \text{(1)}\quad & \overrightarrow{\mathrm{diam}}(G) \leq 2(|A| - d(u)) + 7 && \text{if $G$ is undirected;\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } \\ \text{(2)}\quad & \overrightarrow{\mathrm{diam}}(G) \leq 2(|A| - d^*(u)) + 8 && \text{if $d_G^{+}(u)+d_G^{-}(u)\ge 2$;} \\ \text{(3)}\quad & \overrightarrow{\mathrm{diam}}(G) \leq 2(|A| - d^*(u)) + 10 && \text{otherwise}. \end{align*} All of the above bounds are sharp, except possibly the last one.

23 pages, 6 figures