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, \ldots, n_p)) = d(G)\),
where \(G(n_1, n_2, \ldots, n_p)\) is a \(G\)-vertex multiplication
([2]) of a connected bipartite graph \(G\) of order \(p \geq 3\)
with diameter \(d(G) \geq 5\) and any finite sequence \(\{n_1, n_2, \ldots, n_p\}\)
with \(n_i \geq 3\).