The Kirchhoff Index of Folded Hypercubes and Some Variant Networks

The -dimensional folded hypercube is an important and attractive variant of the -dimensional hypercube , which is obtained from by adding an edge between any pair of vertices complementary edges. is superior to in many measurements, such as the diameter of which is , about a half of the diameter in terms of . The Kirchhoff index is the sum of resistance distances between all pairs of vertices in . In this paper, we established the relationships between the folded hypercubes networks and its three variant networks , , and on their Kirchhoff index, by deducing the characteristic polynomial of the Laplacian matrix in spectral graph theory. Moreover, the explicit formulae for the Kirchhoff indexes of , , , and were proposed, respectively. 1. Introduction It is well known that interconnection networks play an important role in parallel communication systems. An interconnection network is usually modelled by connected graphs , where denotes the set of processors and denotes the set of communication links between processors in networks. In this work, we are concerned with finite undirected connected simple graphs (networks). For the graph theoretical definitions and notations, we follow [1]. The adjacency matrix of is an matrix with the entry equal to 1 if vertices and are adjacent and 0 otherwise. Suppose that is the degree diagonal matrix of , where is the degree of the vertex , . Let be called the Laplacian matrix of . Then, the eigenvalues of and are called eigenvalues and Laplacian eigenvalues of , respectively. For more details, we refer to [1]. Let be a graph with vertices labelled . The resistance distances between vertices and , denoted by , are defined to be the effective electrical resistance between them if each edge of is replaced by a unit resistor [2]. A famous distance-based topological index as the Kirchhoff index Kf( ), is defined as the sum of resistance distances between all pairs of vertices in . Define known as the Kirchhoff index of [2]. The Kirchhoff index attracted extensive attention due to its wide applications in physics, chemistry, graph theory, and so forth [3–6]. For example, Zhu et al. [7] and Gutman and Mohar [8] proved that relations between Kirchhoff index of a graph and Laplacian eigenvalues of the graph. The Kirchhoff index also is a structure descriptor [9]. However, it is difficult to design some algorithms [7, 10, 11] to calculate resistance distances and the Kirchhoff indexes of graphs. Hence, it makes sense to find explicit closed form for some special classes of graphs, for instance, the Kirchhoff index for cycles and