On the distance eigenvalues of Cayley graphs

Abstract

In this paper, graphs are undirected and loop-free and groups are finite. By Cn, Kn and Km,n we mean the cycle graph with n vertices, the complete graph with n vertices and the complete bipartite graph with parts size m and n, respectively. Also by Zn and Sn, we mean the cyclic group of order n and the symmetric group on n symbols, respectively. Let Γ be a simple connected graph with vertex set {v1,…,vn}. The distance between vertices vi and vj, denoted by d(vi,vj), is the length of a shortest path between them. The distance matrix of Γ, denoted by DΓ, is an n×n matrix whose (i,j)-entry is d(vi,vj). The distance characteristic polynomial of Γ, denoted by χD(Γ) is det(λI-D) and its zeros are the distance eigenvalues (in short D-eigenvalues) of Γ. If λ is a D-eigenvalue of Γ with multiplicity m, then we denote it by λ[m]. Let λ1≥λ2≥…≥λn are the D-eigenvalues of Γ. Then λ1 is called distance spectral radius of Γ and we denote it by ρ(Γ). Also the multiset {λ1,…,λn} is denoted by SpecD(Γ). 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 G be a group and S=S-1 be a subset of G not containing the identity element of G. The Cayley graph of G with respect of S, denoted by Cay(G,S), is a graph with vertex set G and edge set {{g,sg}|g∈G,s∈S}. Cay(G,S) is a simple |S|-regular graph. Let x,y∈G. Then for all g∈G, x and y are adjacent if and only if xg and yg are adjacent. This implies that d(g,h)=d(1,hg-1) and d(g)=d(1) for all g,h∈G, where d(x)=y∈G‍d(x,y). 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, Foster-Greenwood 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 Γ=Cay(G,S) be a Cayley graph over a finite group G. It is well-known that one can determine the (adjacency) eigenvalues Γ by the irreducible representations of G, 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 G. Then, as an application of our result, we exactly determine the distance eigenvalues of some well-know Cayley graphs: cycles, n-prims, hexagonal torus network and cubic Cayley graphs over abelian groups. Results and discussion We construct an infinite family of distance integral Cayley graphs. Also we prove that a finite abelian group G admits a connected cubic distance integral Cayley graph if and only if G is isomorphic to one of the groups Z4, Z6, Z4×Z2, Z6×Z2, or Z2×Z2×Z2. Furthermore, up to isomorphism, there are exactly 5 connected cubic distance integral Cayley graphs over Abelian groups which are K4, K3,3, P3, P4 and P6, where Pn is the n-prism. Conclusion 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 n-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.In this paper, graphs are undirected and loop-free and groups are finite. By Cn, Kn and Km,n we mean the cycle graph with n vertices, the complete graph with n vertices and the complete bipartite graph with parts size m and n, respectively. Also by Zn and Sn, we mean the cyclic group of order n and the symmetric group on n symbols, respectively. Let Γ be a simple connected graph with vertex set {v1,…,vn}. The distance between vertices vi and vj, denoted by d(vi,vj), is the length of a shortest path between them. The distance matrix of Γ, denoted by DΓ, is an n×n matrix whose (i,j)-entry is d(vi,vj). The distance characteristic polynomial of Γ, denoted by χD(Γ) is det(λI-D) and its zeros are the distance eigenvalues (in short D-eigenvalues) of Γ. If λ is a D-eigenvalue of Γ with multiplicity m, then we denote it by λ[m]. Let λ1≥λ2≥…≥λn are the D-eigenvalues of Γ. Then λ1 is called distance spectral radius of Γ and we denote it by ρ(Γ). Also the multiset {λ1,…,λn} is denoted by SpecD(Γ). 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 G be a group and S=S-1 be a subset of G not containing the identity element of G. The Cayley graph of G with respect of S, denoted by Cay(G,S), is a graph with vertex set G and edge set {{g,sg}|g∈G,s∈S}. Cay(G,S) is a simple |S|-regular graph. Let x,y∈G. Then for all g∈G, x and y are adjacent if and only if xg and yg are adjacent. This implies that d(g,h)=d(1,hg-1) and d(g)=d(1) for all g,h∈G, where d(x)=y∈G‍d(x,y). 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, Foster-Greenwood 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 Γ=Cay(G,S) be a Cayley graph over a finite group G. It is well-known that one can determine the (adjacency) eigenvalues Γ by the irreducible representations of G, 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 G. Then, as an application of our result, we exactly determine the distance eigenvalues of some well-know Cayley graphs: cycles, n-prims, hexagonal torus network and cubic Cayley graphs over abelian groups. Results and discussion We construct an infinite family of distance integral Cayley graphs. Also we prove that a finite abelian group G admits a connected cubic distance integral Cayley graph if and only if G is isomorphic to one of the groups Z4, Z6, Z4×Z2, Z6×Z2, or Z2×Z2×Z2. Furthermore, up to isomorphism, there are exactly 5 connected cubic distance integral Cayley graphs over Abelian groups which are K4, K3,3, P3, P4 and P6, where Pn is the n-prism. Conclusion The following conclusions were drawn from this research. In this paper, graphs are undirected and loop-free and groups are finite. By Cn, Kn and Km,n we mean the cycle graph with n vertices, the complete graph with n vertices and the complete bipartite graph with parts size m and n, respectively. Also by Zn and Sn, we mean the cyclic group of order n and the symmetric group on n symbols, respectively. Let Γ be a simple connected graph with vertex set {v1,…,vn}. The distance between vertices vi and vj, denoted by d(vi,vj), is the length of a shortest path between them. The distance matrix of Γ, denoted by DΓ, is an n×n matrix whose (i,j)-entry is d(vi,vj). The distance characteristic polynomial of Γ, denoted by χD(Γ) is det(λI-D) and its zeros are the distance eigenvalues (in short D-eigenvalues) of Γ. If λ is a D-eigenvalue of Γ with multiplicity m, then we denote it by λ[m]. Let λ1≥λ2≥…≥λn are the D-eigenvalues of Γ. Then λ1 is called distance spectral radius of Γ and we denote it by ρ(Γ). Also the multiset {λ1,…,λn} is denoted by SpecD(Γ). 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 G be a group and S=S-1 be a subset of G not containing the identity element of G. The Cayley graph of G with respect of S, denoted by Cay(G,S), is a graph with vertex set G and edge set {{g,sg}|g∈G,s∈S}. Cay(G,S) is a simple |S|-regular graph. Let x,y∈G. Then for all g∈G, x and y are adjacent if and only if xg and yg are adjacent. This implies that d(g,h)=d(1,hg-1) and d(g)=d(1) for all g,h∈G, where d(x)=y∈G‍d(x,y). 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, Foster-Greenwood 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 Γ=Cay(G,S) be a Cayley graph over a finite group G. It is well-known that one can determine the (adjacency) eigenvalues Γ by the irreducible representations of G, 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 G. Then, as an application of our result, we exactly determine the distance eigenvalues of some well-know Cayley graphs: cycles, n-prims, hexagonal torus network and cubic Cayley graphs over abelian groups. Results and discussion We construct an infinite family of distance integral Cayley graphs. Also we prove that a finite abelian group G admits a connected cubic distance integral Cayley graph if and only if G is isomorphic to one of the groups Z4, Z6, Z4×Z2, Z6×Z2, or Z2×Z2×Z2. Furthermore, up to isomorphism, there are exactly 5 connected cubic distance integral Cayley graphs over Abelian groups which are K4, K3,3, P3, P4 and P6, where Pn is the n-prism. Conclusion 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 n-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.In this paper, graphs are undirected and loop-free and groups are finite. By Cn, Kn and Km,n we mean the cycle graph with n vertices, the complete graph with n vertices and the complete bipartite graph with parts size m and n, respectively. Also by Zn and Sn, we mean the cyclic group of order n and the symmetric group on n symbols, respectively. Let Γ be a simple connected graph with vertex set {v1,…,vn}. The distance between vertices vi and vj, denoted by d(vi,vj), is the length of a shortest path between them. The distance matrix of Γ, denoted by DΓ, is an n×n matrix whose (i,j)-entry is d(vi,vj). The distance characteristic polynomial of Γ, denoted by χD(Γ) is det(λI-D) and its zeros are the distance eigenvalues (in short D-eigenvalues) of Γ. If λ is a D-eigenvalue of Γ with multiplicity m, then we denote it by λ[m]. Let λ1≥λ2≥…≥λn are the D-eigenvalues of Γ. Then λ1 is called distance spectral radius of Γ and we denote it by ρ(Γ). Also the multiset {λ1,…,λn} is denoted by SpecD(Γ). 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 G be a group and S=S-1 be a subset of G not containing the identity element of G. The Cayley graph of G with respect of S, denoted by Cay(G,S), is a graph with vertex set G and edge set {{g,sg}|g∈G,s∈S}. Cay(G,S) is a simple |S|-regular graph. Let x,y∈G. Then for all g∈G, x and y are adjacent if and only if xg and yg are adjacent. This implies that d(g,h)=d(1,hg-1) and d(g)=d(1) for all g,h∈G, where d(x)=y∈G‍d(x,y). 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, Foster-Greenwood 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 Γ=Cay(G,S) be a Cayley graph over a finite group G. It is well-known that one can determine the (adjacency) eigenvalues Γ by the irreducible representations of G, 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 G. Then, as an application of our result, we exactly determine the distance eigenvalues of some well-know Cayley graphs: cycles, n-prims, hexagonal torus network and cubic Cayley graphs over abelian groups. Results and discussion We construct an infinite family of distance integral Cayley graphs. Also we prove that a finite abelian group G admits a connected cubic distance integral Cayley graph if and only if G is isomorphic to one of the groups Z4, Z6, Z4×Z2, Z6×Z2, or Z2×Z2×Z2. Furthermore, up to isomorphism, there are exactly 5 connected cubic distance integral Cayley graphs over Abelian groups which are K4, K3,3, P3, P4 and P6, where Pn is the n-prism. Conclusion 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 n-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. 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 n-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.

Keywords

• distance matrix
• rreducible representation
• cayley graph
• eigenvalue.