On optimal orientation of cycle vertex multiplications (Q2566147)

An orientation of a graph \(G\) is a digraph obtained from \(G\) by assigning to each edge in \(G\) a direction. An orientation \(D\) of \(G\) is strong if every two vertices in \(D\) are mutually reachable in \(D\). For a connected graph containing no bridges let \({\mathcal D}(G)\) be the family of its strong orientations. Let \(d(G)\) be a diameter of \(G\) and \(d(D)\) be a diameter of the digraph \(D\). The orientation number \(\vec{d}(G)\) is defined as \(\min\{d(D)\mid D\in{\mathcal D}(G)\}\). Let \(G\) be a given connected graph of order \(n\) with vertex set \(V(G)=\{v_1,v_2,\dots,v_n\}\). For any sequence of \(n\) positive integers \((s_i)\), let \(G(s_1,s_2,\dots,s_n)\) denote the graph with vertex set \(V^*\) and edge set \(E^*\) such that \(V^*=\bigcup\nolimits^n_{i=1}V_i\), where the \(V_i\)'s are pairwise disjoint sets with \(| V_i| =s_i\), \(i=1,2,\dots,n\), and for any two distinct vertices \(x,y\) in \(V^*\), \(xy\in E^*\) if and only if \(x\in V_i\) and \(y\in V_j\) for some \(i,j\in\{1,2,\dots,n\}\) with \(i\neq j\) such that \(v_iv_j\in E(G)\). \textit{K. M. Koh} and \textit{E. G. Tay} [Discrete Math. 219, 153-171 (2000; Zbl 0946.05036)] proved that for any connected graph \(G\) of order \(n\geq3\) and any \(n\geq2\) for each \(i=1,2,\dots,n\) there is \(d(G)\leq\vec{d}(G(s_1,s_2,\dots,s_n))\leq d(G)+2\). Due to this results all graphs of the form \(G(s_1,s_2,\dots,s_n)\) are divident into the following three classes: \({\mathcal C}_i=\{G(s_1,s_2,\dots,s_n)\mid \vec{d}(G(s_1,s_2,\dots,s_n))=d(G)+i\}\), \(i=0,1,2\). The main result of this paper is the proof that \(C_n(s_1,s_2,\dots,s_n)\in{\mathcal C}_0\) for all \(n\geq10\) and \(s_i\geq3\) for each \(i=1,2,\dots,n\). Partial results are obtained for \(C_n(3,3,\dots,3)\) for \(6\leq n\leq9\) and \(C_n(4,4,\dots,4)\) for \(n=6,7\).