ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 13 (2017) 207-225
Spectrum, distance spectrum, and Wiener index of wreath products of complete graphs
We describe the adjacency matrix and the distance matrix of the wreath product of two complete graphs, and we give an explicit computation of their spectra. As an application, we deduce the spectrum of the transition matrix of the Lamplighter random walk over a complete base graph, with a complete color graph. Finally, an explicit computation of the Wiener index is given.
Keywords: Wreath product of complete graphs, adjacency matrix, distance matrix, spectrum, distance spectrum, Wiener index.
Math. Subj. Class.: 05C12, 05C50, 05C76, 05C81, 15A69
1 Introduction
The construction of new graphs starting from smaller factor graphs is a very natural and fruitful technique, largely developed in literature for its theoretical interest in several branches of Mathematics - Algebra, Combinatorics, Probability, Harmonic Analysis - but also for its practical applications. Among the standard products we find, for instance, the Cartesian product, the direct product, the strong product, the lexicographic product [22, 23, 30, 31]. More recently, the zig-zag product was introduced [29], in order to produce expanders of constant degree and arbitrary size; in [10, 14], some combinatorial and topological properties of such products, as well as connections with random walks, have been investigated.
It is worth mentioning that many of these constructions play an important role in Geometric Group Theory, since it turns out that, when applied to Cayley graphs of two finite groups, they provide the Cayley graph of an appropriate product of these groups (see [1],
* Telephone: +39 06 45678356, Fax: +39 06 45678379 E-mail address: alfredo.donno@unicusano.it (Alfredo Donno)
Alfredo Donno *
Universitá degli Studi Niccold Cusano via Don Carlo Gnocchi 3, 00166 Roma, Italia
*
Received 31 May 2016, accepted 16 December 2016, published online 3 March 2017
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
208
Ars Math. Contemp. 13 (2017) 107-123
where this correspondence is shown for zig-zag products, or [15], for the case of wreath and generalized wreath products).
Spectral properties of graph products have been object of an intensive study in the last decades, both for their algebraic and combinatorial interest, and for applications to Probability, Computer Science, and Mathematical Chemistry. The spectrum of a graph is defined as the spectrum of its adjacency matrix; similarly, the distance spectrum of a graph is defined to be the spectrum of its distance matrix (see Section 2). The reader can refer, for instance, to the monograph [5] for an exhaustive treatment of spectra of graphs. We also want to mention the papers [24, 25, 34], where the distance spectrum of some graph compositions has been studied.
A related topic of research is the Wiener index, which is defined as the sum of the distances between all the unordered pairs of vertices of the graph. This index was introduced by Wiener [36] and, due to the wide range of applications, it is nowadays largely studied. In particular, it is one of the most frequently used topological indices in mathematical chemistry, as molecules can be represented by means of undirected graphs. For this reason, it has a strong correlation with many physical and chemical properties of molecular compounds, whose properties do not only depend on their chemical formula, but also on their molecular structure [13]. There exists a wide range of fields such as communication, facility location, cryptology, architecture where the Wiener index of a graph is of great interest. A large number of papers is devoted to the study of the Wiener index of graphs, sequences of graphs, products of graphs. In [12] the Wiener index of trees is investigated. In [16] the Wiener index and the related Hosoya polynomial are studied for a family of circulant graphs. See also the paper [9], where the Wiener index is studied on an increasing sequence of finite graphs, introduced in [6], and whose limit graphs have been studied in [7], which approximates the Sierpinski carpet fractal. In [17, 18] the study of Wiener index is developed for some graph compositions.
In the present paper, we focus our attention on a different kind of graph product known in literature, namely the wreath product of two graphs (see Definition 2.1). This construction is nowadays largely studied, and different generalizations have been introduced [15, 19]. Notice that this construction is interesting not only from an algebraic and combinatorial point of view, but also for its connection with Geometric group theory and Probability, via the notions of Lamplighter group and Lamplighter random walk (see, for instance, [3, 21, 32, 33, 37]). Notice that in a previous paper joint with D. D'Angeli [8], we introduced a matrix operation, called wreath product of matrices (recalled in Definition 2.2), which is a matrix analogue of the wreath product of graphs, since it provides the adjacency matrix of the wreath product of two graphs, when applied to the adjacency matrices of the factors (Theorem 2.3 below).
Let us denote by Kn the complete graph on n vertices. In this paper, the wreath product Kn l Km is studied. In Proposition 3.1, we describe in detail distances in Kn l Km, and we deduce its diameter in Corollary 3.2. Moreover, in Proposition 3.4 we show that the graph Kn l Km is not distance-regular. After describing in detail the adjacency matrix of the wreath product Kn l Km of two complete graphs, we are able to explicitly compute its spectrum by using a reduction argument, allowing to reduce our computations to the study of the spectrum of smaller matrices, whose size is the cardinality of the vertex set of the first graph (Theorem 3.7); we then deduce the spectrum of the transition matrix of the Lamplighter random walk with base graph Kn and color graph Km (Corollary 3.9). In Proposition 3.10, we provide the distance matrix of KnlKm, and its spectrum is determined
A. Donno: Spectrum, distance spectrum, and Wiener index of wreath products of.
209
in Theorem 3.11 by means of a second reduction argument. Finally, in Theorem 3.13, the Wiener index of the graph Kn I Km is computed.
Notice that the spectrum considered in the present paper concerns the "walk or switch" Lamplighter random walk. The analogous question for the so called "switch-walk-switch" Lamplighter random walk has been solved in [26, 27]. A common framework for such computations has been established in [20].
2 Preliminaries
Let G = (V, E) be a finite undirected graph, where V denotes the vertex set, and E is the edge set consisting of unordered pairs of type {u, v}, with u, v e V. If {u, v} e E, we say that the vertices u and v are adjacent in G, and we use the notation u ~ v. A path in G is a sequence u0, ui,..., u of vertices such that u ~ ui+1, for each i = 0,..., I - 1. We say that such a path has length I. The graph is connected if, for every u, v e V, there exists a path u0, u1,..., u^ in G such that u0 = u and u = v. For a connected graph G, we will denote by d(u, v) the geodesic distance between the vertices u and v, that is, the length of a minimal path in G joining u and v. The diameter of G is then defined as diam(G) = max„,„Ev {d(u, v)}.
Recall now that the adjacency matrix of an undirected graph G = (V, E) is the square matrix A = (au,v )u,vev, indexed by the vertices of G, whose entry au,v equals the number of edges connecting u and v. As the graph G is undirected, A is a symmetric matrix and so all its eigenvalues are real. The spectrum of G is then defined as the spectrum of its adjacency matrix. The degree of a vertex u e V is defined as deg(u) = J2V£V au,v. In particular, we say that G is regular of degree d, or d-regular, if deg(u) = d, for each u e V. In this case, the normalized adjacency matrix A' of G is obtained as A' = d A.
We recall now the definition of wreath product of graphs.
Definition 2.1. Let G1 = (V1, E1) and G2 = (V2, E2) be two finite graphs. The wreath product G11 G2 is the graph with vertex set V2Vl x V1 = {(f, v) | f: V1 ^ V2, v e V1}, where two vertices (f, v) and (f', v') are connected by an edge if:
(1)	(edges of type I) either v = v' =: v and f (w) = f '(w) for every w = v, and
f (v) ~ f'(v) in G2;
(2)	(edges of type II) or f (w) = f' (w), for every w e V1, and v ~ v' in G1.
It follows from the definition that, if G1 is a regular graph on n1 vertices with degree d1 and G2 is regular graph on n2 vertices with degree d2, then the graph G11G2 is a (d1 + d2 )-regular graph on n^1 vertices.
It is a classical fact (see, for instance, [37]) that the simple random walk on the graph G11G2 is the so called Lamplighter random walk, according to the following interpretation: suppose that at each vertex of G1 (the base graph) there is a lamp, whose possible states (or colors) are represented by the vertices of G2 (the color graph), so that the vertex (f, v) of G1 I G2 represents the configuration of the |V1| lamps at each vertex of G1 (for each vertex u e V1, the lamp at u is in the state f (u) e V2), together with the position v of a lamplighter walking on the graph G1 . At each step, the lamplighter may either go to a neighbor of the current vertex v and leave all lamps unchanged (this situation corresponds to edges of type II in G11 G2), or he may stay at the vertex v e G1, but he changes the state of the lamp which is in v to a neighbor state in G2 (this situation corresponds to edges of type I in G11 G2). For this reason, the wreath product G11 G2 is also called the Lamplighter
210
Ars Math. Contemp. 13 (2017) 107-123
graph, or Lamplighter product, with base graph Gi and color graph G2. Also notice that the model described above is often called "walk or switch" Lamplighter random walk.
It is worth mentioning that the wreath product of graphs represents a graph analogue of the classical wreath product of groups [28], as it turns out that the wreath product of the Cayley graphs of two finite groups is the Cayley graph of the wreath product of the groups, with a suitable choice of the generating sets. In the paper [15], this correspondence is proven in the more general context of generalized wreath products of graphs, inspired by the construction introduced in [2] for permutation groups. Also notice that in [19] a different notion of generalized wreath product of graphs is presented.
In the paper [8], the following matrix construction involving wreath products is introduced. Let Mmxn(C) denote the set of matrices with m rows and n columns over the complex field, and let in be the identity matrix of size n. We recall that the Kronecker product of two matrices A = (a^)i=i,...,m;j=i,...,„ € Mmx„(C) and B = (bhk)h=i,...,p-,k=i,...,q € Mpxq(C) is defined to be the mp x nq matrix
( aiiB • • • ainB A ® B = . ... .
\ amiB • • • amnB
We denote by A0" the iterated Kronecker product A < • • • < A, and we put A0° = 1.
Definition 2.2 ([8]). Let A € Mnxn(C) and B € Mmxm(C). For each i = 1,..., n, let Ci = (chk)h,k=i,...,n € Mnxn(C) be the matrix defined by
= 1 if h = k = i chk = ^ 0 otherwise.
The wreath product of A and B is the square matrix of size nmn defined as
n
A i B = 10" < A + £ if-1 << B <g> << Ci.
i=i
In [8] the following theorem, which shows the correspondence between wreath products of matrices and wreath products of graphs, is proven.
Theorem 2.3. Let A' be the normalized adjacency matrix of a di-regular graph Gi = (Vi,Ei) and let A2 be the normalized adjacency matrix of a d2-regular graph G2 =
(V2,E2). Then the wreath product	A'^ i	A2^ is the normalized adjacency
matrix of the graph wreath product G' iG2.
For a finite connected graph G = (V, E), the distance matrix D = (du,v)u,vev of G is, by definition, the square matrix indexed by the vertices of G, such that du,v = d(u, v). The matrix D is symmetric by definition, so that its spectrum is real. The spectrum of D is usually called the distance spectrum of the graph G.
We complete this preliminary section by recalling the definition of Wiener index of a finite connected graph G = (V, E). The Wiener index of G is defined as the sum of the distances between all the unordered pairs of vertices, i.e.,
W(G) = 1 £ d(u,v),
u,vG V
n times
A. Donno: Spectrum, distance spectrum, and Wiener index of wreath products of.
211
where d(u, v) denotes the usual geodesic distance between u and v.
In Section 3, we will construct the adjacency matrix and the distance matrix of the graph Kn I Km, and we will compute their spectra. Finally, we will provide an explicit computation of the Wiener index of Kn I Km.
3 The wreath product Kn I Km
From now on, we will focus our attention on the wreath product Kn I Km, where Kn (Vn, En) is the complete graph on n vertices, that is, the graph on n vertices in which every pair of distinct vertices is connected by a unique edge. Notice that Kn is a regular graph
of degree n - 1, with diameter 1, where d(u, v) = j ^ if U = V for each pair u, v of
vertices.
Figure 1: The complete graph K6.
In particular, the adjacency matrix of Kn is given by Adn = Jn - /n, where Jn denotes the uniform square matrix of size n, whose entries are all equal to 1. Moreover, it follows from Theorem 2.3 that the adjacency matrix of the graph Kn I Km is the matrix
n
Adn I Adm = /®" ® Adn + ^ if" ® Adm <g> /®"-< ® Cj,	(3.1)
j=1
with Cj as in Definition 2.2. Notice also that, by definition, Kn I Km is an (n + m -2)-regular graph on nmn vertices. A vertex of Kn I Km will be usually denoted by (y1,..., yn)xj, where yj G Vm, for each j = 1,..., n, and xj G Vn. In the lamplighter interpretation, we can think that the lamp placed at the j-th vertex xj of Kn has color yj, with yj G Vm, and the lamplighter is in position xj.
Moreover, it follows from the definition of wreath product of graphs that two vertices u = (y1,..., yn)xj and v = (y'x,..., yn)xk have distance 1 if either there exists a unique index j G {1,..., n} such that yj = yj and xj = xk; or yj = yj for each j, and xj = xk (observe that xj ~ xk in Kn if and only if xj = xk, as the graph Kn is complete).
We are going to develop an explicit analysis of the variability of the distances between two vertices in the graph Kn I Km. Let u = (y1,..., yn)xj and v = (y'x,..., y'n)xk be two vertices of Kn ^ Km. Put J = {1, 2,..., n} and define the partition J = U JUjV by
= {j G J : yj = yj }	Jl,v = {j G J : yj = yj }.	(3.2)
Note that the cardinality | J^ v | can be interpreted as the Hamming distance between the "lamp strings" (y1,..., yn) and (y',..., yn). The following proposition holds.
212
Ars Math. Contemp. 13 (2017) 107-123
Proposition 3.1. Let u = (yu,..., yn)xi and v = (y[,..., y'n )xk be two vertices of Kn I Km and let J0 v and J^ v as in (3.2). Then
d(u, v)
0 if i = k . i
1 if i = k J Ju 'v
1 if i = k = j*
0;
d(u,v) = < 3 if i = j* = k
2 if i = j* = k; or i = j* = k More generally, for 2 < \J1v | < n:
if Ju,v = {j*}.
d(u,v)=\ 2\Ju
2\JU,v\ + 1 if k,i e J0,v
if i e J0,v ,k e JU,v ; or i e JU,v ,k e JU
2\JU.v\- 1 + Sik if i,k e Ju
J1
u,v
0
u,v
with Sik =
1 if i = k 0 if i = k.
Proof. First of all observe that, if = 0, we have yj = yj for each j e J, so that u and v coincide if i = k, whereas they are adjacent, by an edge of type II in Kn I Km, if i = k.
Suppose now J^v = {j*}. In the first case, the vertices u = (yu,... ,yj„,..., yn)xjt and v = (yi,...,yj t,..., yû)xjt, with yjt = y'jt, are adjacent in Kn I Km. In the second case, when i = j* = k, the path
(yi,...,yjt,...,yn)xi ~ (yi,...,yjt,...,yn)xjt ~ (yi,...,yj„,...,yn)

- (yi, ...,y'j t,.. .,Vn)xh
is a path of minimal length joining u and v. In the third case, when i = j* = k, the path
(yi,...,yjt,...,yn)xjt - (yi,...,y'jt,...,yn)xjt - (yi,...,y'jt,...,yn)xk
is a path of minimal length joining u and v; the case i = j* = k is similar.
Now let 2 < | J^ | = h < n, with = {j1,... ,jh}. In other words, the n-tuples (y1,... ,yn) and (y[,... ,y'n) differ exactly in h places, indexed by the elements j1,... ,jh of . In the first case, the path
(yi,...,yji,...,yn)xi - (yi,...,yj1 ,...,yn)xj1 - (yi,...,y'ji,...,yn)xji -- (yi,...,y'ji,...,yn)xj2-----(yi,...,y'j 1,...,yjh_i,...,yn)xjh -
- (y1,...,yjl ,...,yjh_i ,...,yjh , ... , yn)xjh -- (y1,...,yj i ,...,yj h_ i ,...,yjh ,...,yn)xk
is a minimal path joining u and v, and it has length 2h +1. In the second case, when i e J0v, k e J^ v, we can assume, without loss of generality, because Kn is complete, that jh = k, so that the last step is not necessary, and a path of minimal length connecting u and v has length 2h; a similar argument works in the case i e J^ v, k e J0 v. Finally, if i = k and i,k e J^v, we can assume that j1 = i and jh = k. Now, a path of minimal
A. Donno: Spectrum, distance spectrum, and Wiener index of wreath products of.
213
length joining u and v is given by
(yi,...,yji ,...,Vn)xj1 - (yi,...,yj ^ ,...,y„)xj1 - (yi,...,yj 1,..., y„ )a - (yi,..., yj1,..., yj2,..., yn)xj2 -----
(yi,...,yji, .. ., yj 2 ...,yjh_i ,...,yn)xjh-i -
- (yi,..., yji ,...,yj-2 ...,yj , ...,yn)xj -- (yi,...,yji ,...,yjfc_i ,...,yjfc ,...,yn)xj
and has length 2h - 1. In the special case i = k, we need one more step in order to reach the final vertex xk = xj, by means of an edge of type II in Kn I Km.	□
Corollary 3.2. The diameter of the graph Kn I Km is 2n.
Proof. It follows from the proof of Proposition 3.1 that the maximal distance d(u, v) between two vertices u and v of Kn I Km is equal to 2n, and it is obtained when the vertices u, v have the form
u = (yi, .. ., yn)xj v = (yi, .. ., yn)xfc, with yj = yj, for each j = 1,..., n and xj = xk. In fact, we get in this case d(u, v) = 2| Jlv I- 1 + Sjk = 2n - 1 + 1 = 2n.
□
Now, for each i = 0,1,..., 2n, and every vertex u of Kn I Km, we denote by Sj(u) the sphere of radius i centered at u, that is:
Sj(u) = {v € V(Kn ? Km) : d(u,v) = i}.
Because of the complete symmetry of the graph, it is clear that the integer s j = |Si(u)| does not depend on the particular choice of the vertex u. We recall below the classical definition of distance-regular graph (see, for instance, [4], or [5, Chapter 12] for some results about spectral properties of distance-regular graphs, also in connection with association scheme theory).
Definition 3.3. A connected graph G is said to be distance-regular if it is regular and, for any two vertices u, v at distance i, there are exactly cj neighbors of v in Sj-i(u) and bj neighbors of v in Sj+i(u).
If d is the diameter of G, the sequence {b0, bi,..., ci, c2,..., cd} is usually called the intersection array of G; notice that the integers c0 and are undefined.
Proposition 3.4. For every n, m, the wreath product Kn I Km is not distance-regular.
Proof. Consider two vertices of type u = (yi,..., yn)xj and v = (yi,..., yn)xj, with j = i, so that d(u, v) = 1. Now, the neighbors of v having distance 2 from u are exactly the vertices of type (yi,..., yj,..., yn)xj, with yj = yj: the number of such vertices is m - 1. On the other hand, consider the vertex w = (yi,..., yj,..., yn)xj, with yj = yj, so that we still have d(u, w) = 1. It is clear that the neighbors of w having distance 2

214
Ars Math. Contemp. 13 (2017) 107-123
from u are exactly the vertices of type (y^ ..., yj,..., yn)xj, with xj = xj, and they are precisely n - 1. This implies that the coefficient b\ cannot be defined, and this is sufficient to conclude that Kn i Km is not distance-regular.
Also in the case n = m, the graph is not distance-regular. In order to show that, it suffices to consider the vertices u = (yi,..., yn-i, yn)xn and v = (yi,..., y'n_1,yn)xn, with yj = yj for each j = 1,..., n - 1, so that d(u, v) = 2n - 1, according to Proposition 3.1. Now, the neighbors of v having distance 2n from u are exactly the vertices of type (y',..., yn-i, y'n)xn, with y'n = yn: the number of such vertices is n - 1.
On the other hand, consider the vertices w = (yi,..., yn)xj and z = (y',..., y'n)xj, with yj = yj for each j = 1,..., n and xj = xj, so that we still have d(w, z) = 2n - 1. In this case, the unique neighbor of z having distance 2n from w is the vertex (y',..., y'n)x^ This implies that the coefficient b2n-i cannot be defined, and this is sufficient to conclude that Kn i Kn is not distance-regular.	□
Example 3.5. Consider the graph K3 i K2 depicted in Figure 2, where the vertices of K3 and K2 are identified with the sets {0,1,2} and {0,1}, respectively. The adjacency matrices of the graphs K3 and K2 are, respectively,
011 Ad3 = ( 1 0 1 1 1 0
and
Ad2 =
01 10
so that the matrix wreath product
Ad3 I Ad2 = if3 <g> Ad3 + Ad2 <g> /2 <g> /2 <g> C +
+ /2 <g> Ad2 ® /2 ® C2 + /2 ® /2 ® Ad2 ® C3
is the adjacency matrix of the graph K3IK2. The graph K3 ^ K2 is regular of degree 3, and its diameter is 6.
3.1 Spectrum of the graph Kn I Km
In this section, we will give an explicit description of the spectrum of the graph Kn I Km which is, by definition, the spectrum of its adjacency matrix Adn I Adm described in Equation (3.1). In order to develop our analysis, we need to recall the definition of circulant matrix. A (complex) circulant matrix C of size m is a square matrix with m rows and m columns, of type
C
i co
ci
Cm-1 Co Ci
c1
cm1
cm -1^
c1
co
with Ci e C, Vi = 0,..., m - 1. (3.3)
The reader can refer to [11] as an exhaustive monograph on circulant matrices.
The following theorem has been proven in [8], by using the spectral analysis developed in [35] for block circulant matrices.
A. Donno: Spectrum, distance spectrum, and Wiener index of wreath products of.
215
000, 0
100, 0
000,1
010, 1
.000, 2
001,1
011, 1
011, 2
010, 0
100, 2
001, 0 101, 0 001, 2 >--P-«r-f 101, 2
101, 1
111, 1
111, 2
011, 0 111, 0 010, 2 110, 2
110, 0
100, 1
110, 1
Figure 2: The graph K3 I K2.
Theorem 3.6. Let A be a square matrix of size n, and let B be a circulant matrix of size m as in (3.3). Then the spectrum E of the matrix A I B is obtained by taking the union of the spectra	of the mn matrices of size n given by

M n'i2'
A + EE ciPUtCt,
t=1 i=0
where ij G {0,1,... ,m — I}, for every j = 1,... ,n, and p = exp (.
In particular, Theorem 3.6 can be applied in order to determine the spectrum of the adjacency matrix
Adn I Adm = /m" ® Adn + ^ Z^ ' ® Adm ®
® Ci,
i=i
since the matrix Adm is a circulant matrix, with c0 = 0 and ci = 1, for each i = 1,... ,m-1. When listing eigenvalues and their multiplicities in the next theorem, and in the rest of the paper, we will write Ah to say that the eigenvalue A has multiplicity h; the multiplicity will be omitted when it is equal to 1. We obtain the following result.
n (n)(m- 1)"
Theorem 3.7. The spectrum E of the graph Kn I Km is E = |Jn=0 Ek
n-1.
with
Eo = {(-2)n-1; n - 2}
Efc = (m - 2)k ; (-2)
k— 1 ( o^n— k — 1 m+n-(m-n)2 +4 km
k = 1, .. . ,n — 1

2
216
Ars Math. Contemp. 13 (2017) 107-123
and
£„ = {(m - 2)n-1; m + n - 2} .
Proof. By virtue of Theorem 3.6, the spectrum of Kn I Km is obtained by taking the union of the spectra	of the matrices
n m— 1
M
il,i2,...,i n _
Adn + E E Ct,
t=1 i=0
where ij e {0,1,..., m - 1}, for each j = 1,..., n, and p = exp (. Notice that c0 = 0 and ci = 1 for each i = 1,...,m — 1. Moreover, the following identity holds:
m— 1
E
i=1
m1
(pi4) = \ (p* )m—1
pi t—1
if it =0
- 1 = -1 if it =0
since p is an m-th root of unity. Therefore, the matrix Mii,i2>...>in can be rewritten as
M11 ,12,...,1 n
Adn + E (m - 1)Ct - E Ct
t:i t=0
t:it = 0
= Jn - In + E (m - 1)Ct - ( E Ct + E Ct ) + E Ct
t:it=0 t:it=0 t:it=0 t:it=0
= Jn - 21 n + m E Ct.
t:it=0
By using iterated conjugations with appropriate elementary permutation matrices, it can be shown that the spectrum of the matrix M11'12' . '1" only depends on the number k of indices equal to 0 in the n-tuple (i1, i2,..., in), but it is independent of the particular position of such indices. As a consequence, for each k = 0,1,..., n, we can reduce to investigate the spectrum of the matrix M0'...'0'ik+i'...,in, corresponding to the n-tuple (0,..., 0, ik+1,..., in), with ij = 0 for each j = k + 1,..., n. We have:
k times
( -1 + m 1
M 0'...'0'1k + 1'...'1n
1
Then we can write M^-A«^1'...'1"
1 -1 + m 1
1
1
1 -1
Jn + Q, where Q = m^t=1 Ct - 2/n is the
1
1
1
1
1
A. Donno: Spectrum, distance spectrum, and Wiener index of wreath products of.
217
diagonal matrix
( -2 + i
Q =
-2 + m
2
-2
Now we have:
det(A/„ - MO-.A^+i-.^) =
det (A/„ - J„ - Q)
det ((A/„ - Q) (/„ - (A/„ - Q) —1 J„)) det(A/„ - Q) • det (/„ - (A/„ - Q) —1 J„)
It is clear that
det(A/„ - Q) = (A - (m - 2))k • (A + 2)
n —k
(3.4)
Now it can be seen that the matrix (A/n - Q) 1 Jn is the matrix of rank 1, whose first k rows are constant, with entries all equal to A—^_2), whereas the remaining n - k rows
are
constant, with entries all equal to a+2. Therefore, (A1n - Q)_1 Jn has n - 1 eigenvalues equal to 0, and one eigenvalue equal to A—(,m_2) + n+f. This implies that the matrix In - (A1n - Q)_1 Jn has n - 1 eigenvalues equal to 1, and one eigenvalue equal to 1 -—T—— T_f, so that:
A —(m-2) A+2 '
det (/„ - (A/„ - Q)-1J„) = 1 -
n — k
A - (m - 2) A + 2'
(3.5)
By gluing together (3.4) and (3.5), we obtain:
det(A/„ - Mo,...,°,ik+i,...,in) = (a - (m - 2))k-1 • (A + 2)
\n—k—1
(A2 + (4 - m - n)A + mn + 4 - km - 2n - 2m).
For the particular value k = 0, we get:
det(A/„ - Ml1r",t°) = (A + 2)n—1 • (A - (n - 2)); for the particular value k = n, we have:
det(A1n - M0'...'0) = (A - (m - 2))n—1 • (A - (m + n - 2)).
The claim follows, if we observe that, for each k = 0,1,..., n, the spectrum of Ef must be considered (n) • (m - 1)n—f times, corresponding to the number of n-tuples (i1,..., in) with k indices equal to 0, and the remaining indices varying in {1,...,m - 1}.	□
k
218
Ars Math. Contemp. 13 (2017) 107-123
Example 3.8. Consider the graph K3 l K4, so that n — 3 and m — 4. The spectrum of the matrix Ad3 l Ad4 consists of the following eigenvalues:
5; 211; 127; (-2)81;	(^V.
The corresponding matrices M11 ,i2'®3 of size 3, with i1, i2, i3 G {0,1, 2, 3}, have eigenvalues:
(a)	(-2)2; 1, for k — 0. For instance, this is the case of the matrix
-1 1 1 M1-1-1 — J3 - 2/3 — | 1 -1 1
1 1 -1
(b)	-2; , for k — 1. For instance, this is the case of the matrix
3 1 1
M0-1'1 — J3 - 2/3 + 4C1 — | 1 -1 1
1 1 -1
(c)	2; 3±233, for k — 2. For instance, this is the case of the matrix
3 1 1
M°'°'1 — J3 - 2/3 + 4(C1 + C2) — ( 13 1
V1 1 -1
(d)	22; 5, for k — 3. This is the case of the matrix
__	3 11
M— J3 - 2/3 + 4(C1 + C2 + C3) — J3 + 2/3 — ( 1 3 1
113
Corollary 3.9. The spectrum Y' of the transition matrix of the Lamplighter random walk with base graph Kn and color graph Km is y — u n=° s/fc(n)-(m-1)"_ , with
\ n-1
Y' _ J I	2 \	. n-2
° | \ m+n-2 J ; m+n-2
Y' — / ( m-2 ^fc-1 • (_ 2 \n-fc-1 , m+n-4±^(m-n)2+4fcm
Yk 1 ^ m+n-2 y ; ^ m+n-2 J	;	2(m+n-2)
for k — 1,..., n - 1, and
\ n-1
y — ^ [mm-^ ; 1
Proof. It suffices to take into account that the transition matrix of the Lamplighter random walk on the base graph Kn, with color graph Km, is the normalized adjacency matrix of the graph Kn l Km, which is a regular graph of degree m + n - 2.	□
A. Donno: Spectrum, distance spectrum, and Wiener index of wreath products of.
219
3.2 Distance spectrum and Wiener index of the graph Kn I Km
The aim of this section is to describe the distance matrix of the graph Kn l Km, together with its spectrum. Moreover, we will exhibit an explicit computation of the Wiener index of the graph.
Proposition 3.10. The distance matrix of the graph Kn i Km is the matrix
D =
(i
E
,i„)e{0,i}n
Adm <g> Adm <g> ■ ■ ■ <g> Adm <g> A.
il,i2,
(3.6)
where we put AdPm = Im, and the matrix Ai1,i2,...,in is the square matrix of size n, indexed by the vertices of Kn, defined as follows. Let {ii,..., in} = I0 U Ii, with I0 = {ij : ij = 0} and Ii = {ij : ij = 1}. Then, for any pair of vertices xi and xk of Kn:
(a) Ah,...,in = Adn = Jn - In if Ii = 0/
1 if i = k = j 3 if i = j* = k
2 if i = j* = k; or i = j*
2|Ii| + 1	if i,k e Io
2|Ii|	if i e I0,k e Ii; or i e Ii,k e I0
21Ii | — 1 + Sik if i,k e Ii
1 if i = k 0 if i = k.
(b)	Ai1,...,in(xi,xk)
(c)	Ai1,...,in(xi,xk)
if h = {ij,};
k
if 2 < |I1| < n, where Sik
Proof. Observe that, for each j = 1,..., n, the index ij G {0,1} establishes whether the color of the lamp at the j-th vertex xj of Kn is changed. More precisely, the index ij = 0 produces the matrix AdPm = Im as j-th term of the Kronecker product, so that we are not changing the color of the lamp in that position; conversely, the index ij = 1 provides the matrix Adm as j-th term of the Kronecker product, so that we are changing the color of the lamp in that position, with any other color, as Km is the complete graph. Therefore, for any fixed n-tuple (i1, ...,in ) G {0,1}n, the contribution Adm ®Adm ■ -<8>Adm ®Aiui2..in to D must take into account the distances between vertices u, v of Kn i Km corresponding to lamp configurations which differ exactly at the places indexed by I1 . Therefore, if the configurations of lamps corresponding to the vertices u = (y1,... ,yn)xi and v = (y1,..., y'n)xk of Kn i Km differ at exactly |I11 vertices of Kn, indexed by I1, the last contribution in the Kronecker product is an n x n matrix, whose entry (xi, xk) must be equal to the distance d(u, v). Then the claim follows from Proposition 3.1.	□
As in the case of the adjacency matrix Adn i Adm, the spectrum of the matrix D can be computed by using a reduction argument. In fact, the matrix D in (3.6) has the following block circulant structure
D0
Dm
D
D1
Do
D
m— 1
\

D0 D1
D
m1
D1 Do ••• Dm—1
D1 D0
(3.7)

220
Ars Math. Contemp. 13 (2017) 107-123
with
Do = E Adm &•••& Adm <g> Ao,i2,...,i„
(¿2,...,i„)e{o,i}n
Di = E Admm <g> — <8> Admm <g> AM2,...,in for each i = 1,...,m - 1.
(¿2,...,i„)e{o,i}n
Then the spectral analysis of block circulant matrices developed in [35] ensures that the spectrum of D can be obtained by taking the union of the spectra of the following m matrices of size nmn-i:
m — i
Djl = E phljl Dh1 hi=0
= e Adm Admm ® Ao,i2,...,i„ +
(¿2,...,i„)e{o,i}n m—i
+ E ph1j1 E Adm Adm ® a^,...,^
hi=i	(¿2,...,i„)e{o,i}n
(m —i	\
Ao,i2,...,i„ + E PhljlAi,i2,...,iJ ,
. hl = i /
with j € {0,1,..., m - 1}. Observe that each of these matrices is still a block circulant matrix, with blocks of size nmn—2, given by
(m—i	\
Ao,o,ia,...,i„ + E PhljlAi,o,ia,...,iJ ,
hl=i
(m—i	\
Ao,i,ia,...,i„ + E PhljlAi,i,ia,...,i„
hl=i
for i = 1,..., m - 1. Therefore, the same argument can be repeated, so that the spectrum of D is obtained by taking the union of the spectra of the following m2 matrices of size
n2
nmn 2:
m-i
Djl,j2 = E ph2j2 Dh2 =
h2=o
(m—i	\
Ao,o,ia,...,i„ + E Phl jl Ai,o,i3,...,iJ +
. , . , ,	hl = i	J
m-i
+ E ph2j2 E Adm «>•••«> Admm ®
h2=i	(¿3,...,i„)e{o,i}n
mi
® Ao,i,i3,...,i„ + E PhljlAi,i,i3,...,i„
hl = i
A. Donno: Spectrum, distance spectrum, and Wiener index of wreath products of.
221
£ Ad% ® ■ ■ ■ ® Adm ® i Ao,o,i 3 ,...,<„+
(¿3,...,i„)e{o,i}n	V
m—1	m—i
+ £ phijiAi,o,i3,...,i„ + £ Ph2j2Ao,i,<3,...,i„+
hi = 1 h2 = 1
m—1	m— 1	^
+ £ Phljl £ Ph2j2 A1,1,i3,...,in h i = 1 h2 = 1 /
with (j1, j2) € {0,..., m - 1}2. This reduction argument can be iterated further, until we get blocks of size n. Once again, notice that	Phjs = j m_1 1 if js =0 We
thus have proven the following theorem.
Theorem 3.11. The distance spectrum E of the graph Kn I Km is obtained by taking the union of the spectra Ej1,...,jn of the mn matrices of size n:
n /m— 1	\ is
Dji,.j = £ ^ £ phsjs Aii,...,i„,
(il ,...,i„)£{o,1}n S=1 Vhs = 1	J
(j 1,. .., jn) €{0,...,m - 1}n, where, if we put Io = {ij : ij = 0} and I1 = {ij : ¿j = 1}, we have:
Ao,...,o = Adn;
{1 if i, k € I1
3 if i,k € Io	for |I1| = 1;
2 if i € I1, k € Io; or i € Io, k € I1
and
( 2|I1| + 1	ifi,k € Io
Aii,...,in (xi,Xk) = < 21111	if i € Io,k € I1; i € I1,k € Io
[2|A|- 1 + Sik ifi,k € I1
for 2 < |I1| < nwith Sik = j 0 ifi=k
Example 3.12. Let us consider the explicit example K3 I K3. The distance matrix of this graph is
D = I3 ® I3 ® I3 ® Aooo + I3 ® I3 ® Ad3 ® Aoo1 + I3 ® Ad3 ® I3 ® Ao1o+ + I3 ® Ad3 <g> Ad3 <g> Aon + Ad3 <g> I3 <g> I3 <g> A1oo + Ad3 <g> I3 <g> Ad3 <g> A1o1 + + Ad3 ® Ad3 ® I3 ® Ano + Ad3 ® Ad3 ® Ad3 ® Am,
with
0	1 1	3 3 2 Aooo = | 10 1 I Aoo1 = | 3 3 2
1	1 0 2 2 1
222
Ars Math. Contemp. 13 (2017) 107-123
A,
010
A
100
A
110
3	2 3 2 1 2 323
122 233 233
4	3 4
3	4 4
4	4 5
A
011
A
101
A
111
The spectrum of D consists of the following eigenvalues:
544 443 434
443 454 344
6 5 5 5 6 5 5 5 6
312; 152; 048; (-3)18; (-24 ± 3V43)6
We have, for instance:
D0,2,0 = A000 + 2A001 - A010 - 2A011 + 2A100 + 4A101 - 2A110 - 4Am =
-21 -9 -18 -9 -9 -9 -18 -9 -21
whose eigenvalues are -3 and -24 ± 3v/43.
Next, we pass to the computation of the Wiener index W(Kn l Km) of the graph Kn l Km. It follows from the definition of the Wiener index that W (Kn l Km) is given by the sum of all the entries of D, divided by 2, due to the fact that each contribution d(u, v) appears twice, as the matrix D is symmetric. Keeping in mind the block structure of the distance matrix D described in (3.7) and the fact that each block Dj, for i = 0,..., m -1, appearing in (3.7) can be recursively regarded as a block circulant matrix, until one gets elementary blocks of size n represented by matrices of type Ailv..,in, we obtain the following result.
Theorem 3.13. The Wiener index of the graph Kn l Km is
W(Kn l Km) = nmn(2mnn2 - nmn - 2n2mn-1 + mn + 2nmn-1 - mn-1 - m). Proof. First of all, for every n-tuple (i1,...,in) G {0,1}n, put:
dj
■i1,...,i„
Ail,...,in (x
Xi,Xj G Vn

).
Now observe that, by definition of the matrices Ail,...,in, the sum dil,...,in only depends on the cardinality of the sets 10 = {i3 : i3 = 0} and 11 = {i3 : i3 = 1}, while it is independent from the particular position of the indices. Therefore, for every k = 0,1,..., n, it makes sense to define:
dk = Y^ A1, ..., 1,0,..., 0(xi,x3).
Xi,Xj G Vn
k times n-k times
Moreover, by performing a direct computation which uses the explicit description of the matrices Ail,...,in given in Theorem 3.11, we are able to determine:
A. Donno: Spectrum, distance spectrum, and Wiener index of wreath products of.
223
(a)	d0 = n(n — 1);
(b)	di = 1 + 4(n — 1) + 3(n — 1)2;
(c)	dk = (2k + 1)(n — k)2 +4k2(n — k) + 2k2 + k(k — 1)(2k — 1) for 2 < k < n.
Now we have to establish the number of contributions of type dk to W(Kn I Km), for every k. First of all, a factor equal to (n) appears, taking into account all the possible choices of k indices equal to 1. Moreover, a second factor given by mn(m — 1)k appears, since a fixed n-tuple (i1,... ,in) containing k indices equal to 1 (see Equation (3.6)) produces mn (m — 1)k blocks of size n, within the matrix D, which are equal to Aj j , due to the fact that, when we change the color of a lamp, we have m — 1 possibilities for the choice of the new color. This implies that
Example 3.14. Consider the case of K3 I K3. Theorem 3.13 gives W(K3 I K3) = 12636, with d0 = 6; d1 = 21; d2 = 35; d3 = 48.
References
[1]	N. Alon, A. Lubotzky and A. Wigderson, Semi-direct product in groups and zig-zag product in graphs: connections and applications, in: 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, Nevada, 2001), IEEE Computer Soc., Los Alamitos, California, pp. 630637, 2001, doi:10.1109/SFCS.2001.959939.
[2]	R. A. Bailey, C. E. Praeger, C. A. Rowley and T. P. Speed, Generalized wreath products of permutation groups, Proc. London Math. Soc. 47 (1983), 69-82, doi:10.1112/plms/s3-47.1.69.
[3]	L. Bartholdi and W. Woess, Spectral computations on lamplighter groups and Diestel-Leader graphs, J. Fourier Anal. Appl. 11 (2005), 175-202, doi:10.1007/s00041-005-3079-0.
[4]	A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, volume 18 of Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer-Verlag, Berlin, 1989, doi: 10.1007/978-3-642-74341-2.
[5]	A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Universitext, Springer-Verlag, New York, 2012, doi:10.1007/978-1-4614-1939-6.
[6]	D. D'Angeli and A. Donno, Isomorphism classification of infinite Sierpinski carpet graphs, AIP Conf. Proc. 1648 (2015), 570002, doi:10.1063/1.4912788, proceedings of the International Conference on Numerical Analysis and Applied Mathematics 2014.
[7]	D. D'Angeli and A. Donno, Metric compactification of infinite Sierpinski carpet graphs, Discrete Math. 339 (2016), 2693-2705, doi:10.1016/j.disc.2016.04.023.
[8]	D. D'Angeli and A. Donno, Wreath product of matrices, Linear Algebra Appl. 513 (2017), 276-303, doi:10.1016/j.laa.2016.10.023.
[9]	D. D'Angeli, A. Donno and A. Monti, Computing the Wiener index in Sierpinski carpet graphs, AIP Conf. Proc. 1738 (2016), 270008, doi:10.1063/1.4952047, proceedings of the International Conference on Numerical Analysis and Applied Mathematics 2015.
[10] D. D'Angeli, A. Donno and E. Sava-Huss, Connectedness and isomorphism properties of the zig-zag product of graphs, J. Graph Theory 83 (2016), 120-151, doi:10.1002/jgt.21917.
(3.8)
By explicitly computing the sum in (3.8), we get the claim.
□
224	Ars Math. Contemp. 13 (2017) 107-123
[11]	P. J. Davis, Circulant Matrices, Pure and Applied Mathematics, John Wiley & Sons, New York, Chichester, Brisbane, Toronto, 1979.
[12]	A. A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math. 66 (2001), 211-249, doi:10.1023/a:1010767517079.
[13]	A. A. Dobrynin, I. Gutman, S. Klavzar and P. Zigert, Wiener index of hexagonal systems, Acta Appl. Math. 72 (2002), 247-294, doi:10.1023/a:1016290123303.
[14]	A. Donno, Replacement and zig-zag products, Cayley graphs and Lamplighter random walk, Int. J. Group Theory 2 (2013), 11-35, http://ijgt.ui.ac.ir/article_1932. html.
[15]	A. Donno, Generalized wreath products of graphs and groups, Graphs Combin. 31 (2015), 915-926, doi:10.1007/s00373-014-1414-4.
[16]	A. Donno and D. Iacono, Distances and isomorphisms in 4-regular circulant graphs, AIP Conf. Proc. 1738 (2016), 270002, doi:10.1063/1.4952041, proceedings of the International Conference on Numerical Analysis and Applied Mathematics 2015.
[17]	M. Eliasi, G. Raeisi and B. Taeri, Wiener index of some graph operations, Discrete Appl. Math. 160 (2012), 1333-1344, doi:10.1016/j.dam.2012.01.014.
[18]	M. Eliasi and B. Taeri, Four new sums of graphs and their Wiener indices, Discrete Appl. Math. 157 (2009), 794-803, doi:10.1016/j.dam.2008.07.001.
[19]	A. Erschler, Generalized wreath products, Int. Math. Res. Notices 2006 (2006), 57835, doi: 10.1155/imrn/2006/57835.
[20]	L. Grabowski, On Turing dynamical systems and the Atiyah problem, Invent. Math. 198 (2014), 27-69, doi:10.1007/s00222-013-0497-5.
[21]	R. I. Grigorchuk and A. Zuk, The lamplighter group as a group generated by a 2-state automaton, and its spectrum, Geom. Dedicata 87 (2001), 209-244, doi:10.1023/a:1012061801279.
[22]	R. Hammack, W. Imrich and S. Klavzar, Handbook of Product Graphs, Discrete Mathematics and its Applications, CRC Press, Boca Raton, Florida, 2nd edition, 2011, doi:10.1201/b10959.
[23]	W. Imrich and H. Izbicki, Associative products of graphs, Monatsh. Math. 80 (1975), 277-281, doi:10.1007/BF01472575.
[24]	G. Indulal, Distance spectrum of graph compositions, Ars Math. Contemp. 2 (2009), 93-100, http://amc-journal.eu/index.php/amc/article/view/10 3.
[25]	G. Indulal and I. Gutman, On the distance spectra of some graphs, Math. Commun. 13 (2008), 123-131,http://hrcak.srce.hr/2 35 6 9.
[26]	F. Lehner, On the eigenspaces of lamplighter random walks and percolation clusters on graphs, Proc. Amer. Math. Soc. 137 (2009), 2631-2637, doi:10.1090/S0002-9939-09-09869-4.
[27]	F. Lehner, M. Neuhauser and W. Woess, On the spectrum of lamplighter groups and percolation clusters, Math. Ann. 342 (2008), 69-89, doi:10.1007/s00208-008-0222-7.
[28]	J. D. P. Meldrum, Wreath Products of Groups and Semigroups, volume 74 of Pitman Monographs and Surveys in Pure and Applied Mathematics, Longman, Harlow, 1995.
[29]	O. Reingold, S. Vadhan and A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders, Ann. of Math. 155 (2002), 157-187, doi:10.2307/3062153.
[30]	G. Sabidussi, The composition of graphs, Duke Math. J 26 (1959), 693-696, doi:10.1215/ S0012-7094-59-02667-5.
[31]	G. Sabidussi, Graph multiplication, Math. Z. 72 (1959), 446-457, doi:10.1007/bf01162967.
[32]	F. Scarabotti and F. Tolli, Harmonic analysis of finite lamplighter random walks, J. Dyn. Control Syst. 14 (2008), 251-282, doi:10.1007/s10883-008-9038-8.
A. Donno: Spectrum, distance spectrum, and Wiener index of wreath products of.
225
[33]	F. Scarabotti and F. Tolli, Harmonic analysis on a finite homogeneous space, Proc. London Math. Soc. 100 (2010), 348-376, doi:10.1112/plms/pdp027.
[34]	D. Stevanovic and G. Indulal, The distance spectrum and energy of the compositions of regular graphs, Appl. Math. Lett. 22 (2009), 1136-1140, doi:10.1016/j.aml.2008.11.007.
[35]	G. J. Tee, Eigenvectors of block circulant and alternating circulant matrices, New Zealand J. Math. 36 (2007), 195-211, http://nzjm.math.auckland.ac.nz/index. php/Eigenvectors_of_Block_Circulant_and_Alternating_Circulant_ Matrices.
[36]	H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947), 17-20, doi:10.1021/ja01193a005.
[37]	W. Woess, A note on the norms of transition operators on lamplighter graphs and groups, Internal J. Algebra Comput. 15 (2005), 1261-1272, doi:10.1142/S0218196705002591.