Optimal Orientations of $G$-Vertex Multiplications of Bipartite Graphs

Abstract

For a graph $G$, let $\mathcal{D}(G)$ be the set of all strong orientations of $G$.
Define the orientation number of $G$, $\overrightarrow{d}(G)=min\{d(D)\mid D\in \mathcal{D}(G)\}$,
where $d(D)$ denotes the diameter of the digraph $D$.

In this paper, it is shown that $\overrightarrow{d}(G(n_1,n_2,\dots ,n_p))=d(G)$,
where $G(n_1,n_2,\dots ,n_p)$ is a $G$-vertex multiplication
([2]) of a connected bipartite graph $G$ of order $p\ge 3$
with diameter $d(G)\ge 5$ and any finite sequence $\{n_1,n_2,\dots ,n_p\}$
with $n_i\ge 3$.