On optimal orientations of tree vertex-multiplications

Abstract

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(T(s1, s2, ..., sn)), where T(s1,s2, ..., sn) is a T vertex-multiplication for any tree T of order n ≥4 and diameter at least 3, and any sequence (si) with si ≥ 2, i = 1,2, ..., n. We show that d{T(s1, s2, ..., sn)) ≤ d(T) + 1 with d{T(s1, s2, ..., sn)) = d(T) for most cases.