On the distance eigenvalues of Cayley graphs

In this paper, graphs are undirected and loop-free and groups are finite. By 𝐶𝑛, 𝐾𝑛 and 𝐾𝑚,𝑛 we mean the cycle graph with 𝑛 vertices, the complete graph with 𝑛 vertices and the complete bipartite graph with parts size 𝑚 and 𝑛, respectively. Also by 𝑍𝑛 and 𝑆𝑛, we mean the cyclic group of order 𝑛 and the symmetric group on 𝑛 symbols, respectively. Let Γ be a simple connected graph with vertex set {𝑣1 , … , 𝑣𝑛}. The distance between vertices 𝑣𝑖 and 𝑣𝑗 , denoted by 𝑑(𝑣𝑖 , 𝑣𝑗), is the length of a shortest path between them. The distance matrix of Γ, denoted by 𝐷Γ, is an 𝑛 × 𝑛 matrix whose (𝑖,𝑗)-entry is 𝑑(𝑣𝑖 , 𝑣𝑗). The distance characteristic polynomial of Γ, denoted by 𝜒𝐷(Γ) is det(𝜆𝐼 − 𝐷) and its zeros are the distance eigenvalues (in short 𝐷-eigenvalues) of Γ. If 𝜆 is a 𝐷-eigenvalue of Γ with multiplicity 𝑚, then we denote it by 𝜆 [𝑚] . Let 𝜆1 ≥ 𝜆2 ≥ ⋯ ≥ 𝜆𝑛 are the 𝐷-eigenvalues of Γ. Then 𝜆1 is called distance spectral radius of Γ and we denote it by 𝜌(Γ). Also the multiset {𝜆1 , … , 𝜆𝑛} is denoted by S𝑝𝑒𝑐𝐷(Γ). The studying of eigenvalues of distance matrices of graphs goes back to 1971, a paper by Graham and Pollack and thereafter attracted much more attention [2]. There are several applications of distance matrix such as the design of communication networks, network follow algorithms, graph embedding theory and in chemistry, for more details see [2]. Let 𝐺 be a group and 𝑆 = 𝑆 −1 be a subset of 𝐺 not containing the identity element of 𝐺. The Cayley graph of 𝐺 with respect of 𝑆, denoted by C𝑎𝑦(𝐺, 𝑆), is a graph with vertex set 𝐺 and edge set {{𝑔, 𝑠𝑔}|𝑔 ∈ 𝐺, 𝑠 ∈ 𝑆}. C𝑎𝑦(𝐺, 𝑆) is a simple |𝑆|-regular graph. Let 𝑥, 𝑦 ∈ 𝐺. Then for all 𝑔 ∈ 𝐺, 𝑥 and 𝑦 are adjacent if and only if 𝑥𝑔 and 𝑦𝑔 are adjacent. This implies that 𝑑(𝑔, ℎ) = 𝑑(1, ℎ𝑔 −1 ) and 𝑑(𝑔) = 𝑑(1) for all 𝑔, ℎ ∈ 𝐺, where 𝑑(𝑥) = ∑𝑦∈𝐺 𝑑(𝑥, 𝑦). In the literature, the adjacency eigenvalues of Cayley graphs have been more widely used than the distance eigenvalues. A graph Γ is called distance (adjacency) integral if all the eigenvalues of its distance (adjacency) matrix are integers. A graph is called circulant if it is a Cayley graph over a cyclic group. Circulant graphs of valency 2 are cycles. In 2001, the distance eigenvalues of cycles computed [6]. In 2010, the distance spectra of adjacency integral circulant graphs characterized and proved that these graphs are distance integral [9]. In 2011, Rentlen discussed the distance eigenvalues of Cayley graphs of Coxeter groups using the irreducible representations of underlying group [10]. He proved that the eigenvalues of the distance matrix of a Cayley graph of a real reflection group with respect to the set of all reflections are integral and provided a combinatorial formula for some such spectra. Then, FosterGreenwood and Kriloff proved that the eigenvalues of the distance, adjacency, and codimension matrices of Cayley graphs of complex reflection groups with connection sets consisting of all reflections are integral and provided a combinatorial formula for the codimension spectra for a family of monomial complex reflection groups [5]. In this paper, we determine the characteristic polynomial of the distance matrix of arbitrary Cayley graphs in terms of the irreducible representations of underlying groups. Let Γ = C𝑎𝑦(𝐺, 𝑆) be a Cayley graph over a finite group 𝐺. It is well-known that one can determine the (adjacency) eigenvalues Γ by the irreducible representations of 𝐺, see for example [3, Corollary 7]. In this paper, by a similar argument, we determine the distance eigenvalues of Γ in terms of the irreducible representations of 𝐺. Then, as an application of our result, we exactly determine the distance eigenvalues of some well-know Cayley graphs: cycles, 𝑛-prims, hexagonal torus network and cubic Cayley graphs over abelian groups.

We construct an infinite family of distance integral Cayley graphs. Also we prove that a finite abelian group 𝐺 admits a connected cubic distance integral Cayley graph if and only if 𝐺 is isomorphic to one of the groups 𝑍4 , 𝑍6 , 𝑍4 × 𝑍2 , 𝑍6 × 𝑍2 , or 𝑍2 × 𝑍2 × 𝑍2 . Furthermore, up to isomorphism, there are exactly 5 connected cubic distance integral Cayley graphs over Abelian groups which are 𝐾4 , 𝐾3,3 , 𝒫3 , 𝒫4 and 𝒫6 , where 𝒫𝑛 is the 𝑛-prism.

The following conclusions were drawn from this research.  The characteristic polynomial of the distance matrix of Cayley graphs over a group G is determined by the irreducible representations of G.  Exact formulas for 𝑛-prisms, hexagonal torus network and cubic Cayley graphs over Abelian groups are given.  Infinite family of distance integral Cayley graphs are constructed.  Cubic distance integral Cayley graphs over finite abelian groups are classified. By a similar argument, one can find all quartic distance integral Cayley graphs over finite Abelian groups.  One can easily compute the distance eigenvalues of a Cayley graph using irreducible representations of the underlying group.