Improving the diameters of completely independent spanning trees in locally twisted cubes

Let G be a graph and denote diam(G) the diameter of G, i.e., the greatest distance between any pair of vertices in G. A set of spanning trees of G are called completely independent spanning trees (CISTs for short) if for every pair of vertices x, y is an element of V (G), the paths joining x and y in any two trees have neither vertex nor edge in common, except x and y. Pai and Chang (2016) [12] recently proposed a unified approach to recursively construct two CISTs in several hypercube-variant networks, including locally twisted cubes. For every kind of n-dimensional variant cube, the diameters of two CISTs for their construction are 2n - 1. In this note, we provide a new scheme to construct two CISTs T-1 and T-2 in locally twisted cubes LT Q(n), and thereby prove the following improvement: for i is an element of {1, 2), diam(T-i) = 2n - 2 if n = 4; and diam(T-i) = 2n - 3 if n >= 5. In particular, the construction of CISTs for LT Q(4) is optimal in the sense of diameter. (C) 2018 Elsevier B.V. All rights reserved.