On optimal orientations of \(G\) vertex-multiplications (Q1567670)

Given a connected graph \(G\) with vertex set \(V(G)=\{v_1, v_2, \dots, v_n\}\) and a sequence of positive integers \(s_1, s_2, \dots, s_n\) one can produce a new graph \(H=G(s_1,s_2,\dots,s_n)\) called \(G\) vertex-multiplication in such a way that each vertex \(v_i\) is multiplied by \(s_i\) (i.e. \(v_i\) is replaced by \(s_i\) independent vertices with equal neighborhoods). E.g. if \(G\) is a complete graph of order \(n\), then \(H\) is a complete \(n\)-partite graph. The authors study the relation between the diameter of \(G\), \(d(G)\), and the minimum diameter of an orientation of \(H\), \(\overline d(H)\). They show that if \(s_i\geq 2\) for each \(i=1,2,\dots,n\) where \(n\geq 3\), then \(\overline d(H)\leq d(G)+2\). As \(d(G)\leq \overline d(H)\), this gives rise to three classes of graphs according to \(\overline d(H)=d(G)+j\), for \(j=0,1,2\). The authors exhibit various families of graphs for each of the classes. E.g., they prove that if \(d(G)\geq 4\) and each \(s_i\geq 4\), then \(j=0\).