On optimal orientations of G vertex-multiplications Original Research Article

For a bridgeless connected graph G, let D(G) be the family of strong orientations of G; and for any D∈D(G), we denote by d(D) (resp., d(G)) the diameter of D (resp., G). Define d̄(G)=min{d(D) | D∈D(G)}. In this paper, we study the problem of evaluating d̄(G(s1,s2,…,sn)), where G(s1,s2,…,sn) is a G vertex-multiplication for any connected graph G of order n⩾3 and any sequence (si) with si⩾2, i=1,2,…,n. While it is trivial that d(G)⩽d̄(G(s1,s2,…,sn)), we show that d̄(G(s1,s2,…,sn))⩽d(G)+2. All graphs of the form G(s1,s2,…,sn) are thus divided into the following three classes: Ci={G(s1,s2,…,sn) | d̄(G(s1,s2,…,sn))=d(G)+i}, i=0,1,2. We exhibit various families of graphs G(s1,s2,…,sn) in Ci for each i=0,1,2.