The correct diameter of trivalent Cayley graphs

Abstract

Let n be a positive integer with n greater than or equal to 2. The trivalent Cayley interconnection network, denoted by TCIN(n), is proposed by Vadapalli and Srimani (1995). Later, Vadapalli and Srimani (1996) claimed that the diameter of TCIN(n) is 2n - 1. In this paper, we argue that the above claim is not correct. Instead, we show that the diameter of TCIN(n) is 2n - 1 only for n = 2 and 2n - 2 for all other cases. (C) 1999 Elsevier Science B.V. All rights reserved.