{'fraction_non_alphanumeric': 0.07064440190966492, 'fraction_numerical': 0.015378522869777573, 'mean_word_length': 3.2369500372856077, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 58, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Some degree and distance-based invariants of wreath products of graphs

The wreath product of graphs is a graph composition inspired by the notion of wreath product of groups, with interesting connections with Geometric Group Theory and Probability. This paper is devoted to the description of some degree and distance-based invariants, of large interest in Chemical Graph Theory, for a wreath product of graphs. An explicit formula is obtained for the Zagreb indices, in terms of the Zagreb indices of the factor graphs. A detailed analysis of distances in a wreath product is performed, allowing to describe the antipodal graph and to provide a formula for the Wiener index. Finally, a formula for the Szeged index is obtained. Several explicit examples are given.


Introduction
The idea of constructing new graphs starting from smaller graphs is very natural and largely developed in literature, for its theoretical interest in several branches of Mathematics -Algebra, Combinatorics, Probability, Harmonic Analysis -but also for its practical applications in Mathematical Chemistry, as graphs are generated in a very natural way from molecules when atoms are replaced by vertices, and bonds by edges. A large number of papers in the last decades has been devoted to graph compositions, and to the investigation of their topological, combinatorial, and spectral properties.
The most classical graph products are the Cartesian product, the direct product, the strong product, the lexicographic product (see [21] and reference therein). More recently, the zig-zag product was introduced [29], in order to produce expanders of constant degree and arbitrary size; in [9,12], some combinatorial and topological properties of such product, 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], where this correspondence is shown for zig-zag products, or [13], for the case of wreath and generalized wreath products).
In the context of graph compositions, an intensively studied topic of research is represented by a number of topological indices, mostly defined in terms of the degree of the vertices of the graph, or in terms of the distance between pairs of vertices. The target in this setting is to describe the considered index of the graph product in terms of the corresponding index of the factor graphs.
Among the most studied degree-based topological indices associated with a graph there are the Zagreb indices, originally introduced by Gutman and Trinajstić in [20] in the early work of the Zagreb Mathematical Chemistry Group on the topological basis of the π-electron energy. Many reformulations and generalizations of such indices have been introduced later in literature, and several connections to many other quantities in Chemical Graph Theory have been pointed out (see also the beautiful book [32]). In the paper [22], the Zagreb indices of some graph compositions have been investigated. A fundamental distance-based index, and probably the most thoroughly examined, 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 [34] 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. 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. A large number of papers is devoted to the study of the Wiener index of graph compositions (see, for instance, the papers [15,16,36]).
Another recently introduced distance-based topological index for graph is the Szeged index, introduced in [19], which coincides with the Wiener index when the considered graph is a tree. In the paper [11], a more general condition to be satisfied in order to have the equality of Wiener and Szeged indices is described. See the paper [25] and references therein for some basic properties of the Szeged index, several chemical applications, and for a description of the Szeged index of a Cartesian product of graphs and some other graph compositions. See [24,25] for bounds on the difference between the Szeged index and the Wiener index of a graph.
In the present paper, we focus our attention on a graph composition known in literature as the wreath product of graphs. This construction is nowadays largely studied, and different generalizations have been introduced [13,17]. 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, [18,30,35]). Moreover, we want to mention that in [8] a matrix operation has been introduced, called wreath product of matrices, 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. In the paper [14] the wreath product of two complete graphs has been investigated: an explicit computation of the spectrum and of the Wiener index has been performed. In the paper [5], jointly with F. Belardo, we have considered the wreath product of a complete graph with a Cocktail Party graph, and we have described its spectrum, together with the Zagreb indices and the Randić index. In the paper [4], jointly with F. Belardo, a more general analysis involving also the study of distances and the computation of the Wiener index has been developed for the wreath product of a complete graph with a cyclic graph.
The aim of this paper is to develop a more general analysis in the more general case of the wreath product of any two graphs. After describing in Section 2 some basic properties of the wreath product of two graphs -connectedness, regularity, vertex-transitivity, bipartiteness (Proposition 2.6) -we investigate in Section 3 two degree-based topological indices of such a product, namely the first and the second Zagreb indices. A formula in the very general case is provided, describing such indices in terms of the corresponding indices of the factor graphs (Theorem 3.1). In Section 4, our attention is focused on the study of distances in a wreath product of any two graphs: an explicit formula is obtained in Theorem 4.11. This analysis enables us to describe eccentricity and diameter in a wreath product (Corollary 4.13), and to describe the antipodal graph (Theorem 4.19). Some more properties of the antipodal graph are obtained in Corollary 4.20 and Proposition 4.21. A large number of detailed examples is presented. The analysis of distances developed in Section 4 allows us to give, in Section 5, a formula for the Wiener index of a wreath product of graph (see Theorem 5.4 and Corollary 5.6): notice that the Wiener index turns out to depend only on the Wiener index of the second factor graph, and on a vector Wiener index associated with the first factor graph (see Definition 5.5). The special cases where the first factor graph is the complete graph, or the path graph, are studied in detail in Sections 5.1 and 5.2. Finally, Section 6 is devoted to the study of the Szeged index. In the general case, we obtain (see Theorem 6.12) a formula in terms of the Szeged index of the second factor graph, and of a sort of generalized Szeged index of the first factor graph (see Definition 6.10), defined for every pair of subsets of its vertices. Under hypothesis of edge-transitivity for the first factor graph, we obtain a strong simplification of this result (Remark 6.15): as an application, we provide an explicit formula for the Szeged index of a wreath product, when the first factor graph is complete (see Theorem 6.16).

Preliminary definitions
Every graph considered in this paper will be finite, undirected, and simple, that is, loops and multiple edges are not allowed, unless explicitly specified. Such a graph will be denoted by G = (V G , E G ), where V G denotes the vertex set, and E G is the edge set consisting of unordered pairs of type {u, v}, with u, v ∈ V G .
If {u, v} ∈ E G , we say that the vertices u and v are adjacent in G, and we write u ∼ v. A path of length ℓ in G is a sequence u 0 , u 1 , . . . , u ℓ of vertices such that u i ∼ u i+1 , for each i = 0, . . . , ℓ − 1. The path is said to be a cycle if u 0 = u ℓ . The graph G is connected if, for every u, v ∈ V G , there exists a path u 0 , u 1 , . . . , u ℓ in G such that u 0 = u and u ℓ = v. For a graph G, we will denote by d G (u, v) the geodesic distance (or distance for short) between the vertices u and v, that is, the length of a shortest path in G joining u and v. We put d G (u, v) = ∞ if there is no path connecting u and v. The eccentricity of a vertex u ∈ V G is defined as e G (u) = max v∈V G {d G (u, v)}. The diameter of G is then defined as diam(G) = max u∈V G {e G (u)}. In particular, the diameter of G is finite if and only if G is a connected graph.
The adjacency matrix of G = (V G , E G ) is the square matrix A = (a u,v ) u,v∈V G , indexed by the vertices of G, such that As the graph G is undirected, A is a symmetric matrix. The degree of a vertex u ∈ V G is then defined as deg u = v∈V G a u,v . In particular, we say that G is regular of degree r G , or r G -regular, if deg u = r G , for each u ∈ V G . In this case, the normalized adjacency matrix A ′ of G is obtained as A ′ = 1 r G A. We recall now the classical definitions of vertex-transitivity, edge-transitivity, arctransitivity (or 1-transitivity) for a graph G = (V G , E G ) (see [33]).
In the rest of the paper, we will denote by Aut(G) the automorphism group of the graph G = (V G , E G ). The transitivity properties of the action of the automorphism group of a graph lead to the following definitions.
Observe that, since the definition of arc-transitivity maps one edge to another, an arc-transitive graph is also edge-transitive. Conversely, an edge-transitive graph need not to be arc-transitive. In [33], Tutte proved that a connected regular graph of odd degree which is both vertex-transitive and edge-transitive is also arc-transitive. In [6], an infinite family of vertex-transitive, edge-transitive, but not arc-transitive regular graphs of even degree is explicitly constructed.
We recall now the fundamental definition of wreath product of graphs.
It is a classical fact (see, for instance, [35]) that the simple random walk on the graph G ≀ H is the so called Lamplighter random walk, according to the following interpretation: suppose that at each vertex of G (the base graph) there is a lamp, whose possible states (or colors) are represented by the vertices of H (the color graph), so that the vertex (f, v) of G ≀ H represents the configuration of the |V G | lamps at each vertex of G (for each vertex u ∈ V G , the lamp at u is in the state f (u) ∈ V H ), together with the position v of a lamplighter walking on the graph G. 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 G ≀ H), or he may stay at the vertex v ∈ G, but he changes the state of the lamp which is in v to a neighbor state in H (this situation corresponds to edges of type I in G ≀ H). For this reason, the wreath product G ≀ H is also called the Lamplighter graph, or Lamplighter product, with base graph G and color graph H.
It follows from Definition 2.3 that if |V G | = n and |V H | = m, the graph G ≀ H has nm n vertices. It is easy to see that G ≀ H is connected if and only if G and H are connected. Moreover, if G is a regular graph of degree r G and H is a regular graph of degree r H , then the graph G ≀ H is an (r G + r H )-regular graph.
Notice that, in the case |V G | = 1, the graph G ≀ H is isomorphic to H; on the other hand, if |V H | = 1, then the graph G ≀ H is isomorphic to G. In the rest of the paper, we suppose that |V G | > 1 and |V H | > 1.
It is worth mentioning that the wreath product of graphs represents a graph analogue of the classical wreath product of groups [26], 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 [13], this correspondence is proven in the more general context of generalized wreath products of graphs, inspired by the construction introduced in [3] for permutation groups.
In the paper [8], the wreath product of two square matrices A of size n, and B of size m, has been defined to be the square matrix of size nm n given by where ⊗ denotes the classical Kronecker product, I m is the identity matrix of size m, and D i = (d hk ) h,k=1,...,n is the square matrix defined by It is also proven in [8] that, if A ′ G is the normalized adjacency matrix of an r G -regular graph G = (V G , E G ) and A ′ H is the normalized adjacency matrix of an r H -regular graph H = (V H , E H ), then the wreath product is the normalized adjacency matrix of the graph G ≀ H.
In Definition 2.3 the set of vertices of G ≀ H is given by Observe that, if |V G | = n and we fix an enumeration for V G := {x 1 , x 2 , . . . , x n }, then there is a natural bijection between the set of maps V V G H and the Cartesian product (V H ) n = V H × · · · × V H n times , so that a vertex w ∈ V G≀H can be written as w = (y, x i ), where y = (y 1 , . . . , y n ) ∈ (V H ) n and x i ∈ V G . In the rest of the paper we will often use also the notation w = (y 1 , . . . , y n )x i for a vertex w of G ≀ H.
It is not difficult to prove that, if G = (V G , E G ) and H = (V H , E H ) are two vertextransitive graphs, then G≀H is a vertex-transitive graph. On the other hand, the properties of edge-transitivity and arc-transitivity are not inherited by the wreath product, the graph K 2 ≀ C 4 being a simple counterexample (see Example 6.17).
We recall here the classical definitions of Cartesian product and direct product of graphs [21].
These graph products are both associative, so that we will use the notation H ✷n and H ×n for the n times iterated Cartesian product and direct product of the graph H with itself, respectively. Remark 2.5. Notice that the graph G ≀ H can be regarded as a subgraph of H ✷n ✷G. This embedding also relates the geodesic distance in H ✷n with the geodesic distance in G ≀ H, as we will point out in Theorem 4.11. Moreover, if we fix (y 1 , . . . , y n ) ∈ (V H ) n , then the subgraph of G ≀ H, induced by the vertices {(y 1 , . . . , y n )x i , i ∈ {1, . . . , n}}, is isomorphic to G. On the other hand, fixing k ∈ {1, . . . , n} and n − 1 vertices of H, let they be y 1 , . . . , y k−1 , y k+1 , . . . , y n , then the subgraph of G ≀ H induced by the vertices {(y 1 , . . . , y k−1 , w, y k+1 , . . . , y n )x k : w ∈ V H }, is isomorphic to H.
We have seen that regularity, connectedness, and vertex-transitivity properties are inherited by the wreath product. In the next proposition, we will focus on the bipartiteness property. For each positive integer n, we will denote by K n the complete graph on n vertices, by C n the cyclic graph on n vertices, and by P n the path graph on n vertices (of length n − 1).
Example 2.7. In Fig. 1, we have represented the graph K 2 ≀ P 3 . Observe that this is a bipartite graph, as both the factors are bipartite. Compare with Fig. 4, where the graph K 2 ≀ C 3 is depicted: this is a non bipartite graph, since the factor C 3 is not bipartite.

Zagreb indices of a wreath product
The Zagreb indices of a finite simple connected graph G = (V G , E G ) were introduced by Gutman and Trinajstić in [20] (see also the more recent survey [27]). The first Zagreb index M 1 (G) is defined as whereas the second Zagreb index M 2 (G) is defined as It follows from the definition that, if G = (V G , E G ) is a regular graph of degree r G on n vertices, so that one has |E G | = nr G 2 , the Zagreb indices are easily given by: The aim of this section is to investigate the Zagreb indices of the wreath product G ≀ H of two finite simple connected graphs G = (V G , E G ) and H = (V H , E H ). We have already remarked that, if G is r G -regular on n vertices and H is r H -regular on m vertices, then the wreath product G ≀ H is a regular graph of degree r G + r H on nm n vertices. If this is the case, then one gets for the wreath product: The following result gives an explicit description of the first and second Zagreb index of a wreath product G ≀ H in terms of the Zagreb indices of the factor graphs, in the more general case where the graphs G and H need not to be regular. and Proof. First of all, note that the degree of the vertex v = (y 1 , y 2 , . . . , y i , . . . , y n )x i of G ≀ H is deg x i + deg y i . By definition, we have: where we have used that the entries y j , with j = i, can vary in V H , together with the fundamental identity which holds for any graph G.
In order to investigate the second Zagreb index, we study the contributions to M 2 (G≀H) given by edges of type I and of type II, separately. We recall that edges of type I have the form (y 1 , y 2 , . . . , y i , . . . , y n )x i ∼ (y 1 , y 2 , . . . , y i , . . . , y n )x i , with y i ∼ y i in H.
Since the entries y j , with j = i, can vary in V H , and we do not want to consider each edge twice, we have to take into account a factor m n−1 2 . Then we have: where we have repeatedly used the definition of the Zagreb indices and the identity (4). Next, we recall that edges of type II have the form (y 1 , y 2 , . . . , y i , . . . , y n )x i ∼ (y 1 , y 2 , . . . , y j , . . . , y n )x j , with x i ∼ x j in G.
Since the entries y h , with h = i, j, can vary in V H , and we do not want to consider each edge twice, we have to take into account a factor m n−2 2 . Then we have: where we have used again the definition of the Zagreb indices and the identity (4). Then, if we glue together the two contributions, we have and we obtain the assert.
Remark 3.2. Note that, in the case of an r G -regular graph G = (V G , E G ) and an r Hregular graph H = (V H , E H ), the formulas (2) and (3) coincide with the formulas given in (1).

Distances in a wreath product
The geodesic distance in a wreath product has been especially studied for Cayley graphs by the investigation of the Word length for wreath products of finite and infinite groups [7,10,23]. In any approach it appears an NP-hard problem: the Traveling Salesman Problem (TSP). It is one of the most intensively studied problem in optimization. The common strategy of these works to avoid the complexity of the TSP is to consider analog easier problems that are, in some sense, approximations for the TSP: it works because most invariants in Geometric Group Theory are defined up to quasi-isometry of groups (and therefore Cayley graphs). Our approach here is purely combinatorial: we push it as far as possible, in the general case, and then we apply the general results to some special classes of graphs. This yields an explicit description of the antipodal graph of a wreath product (Section 4.1) and of some distance-based invariants like the Wiener index (Section 5) and the Szeged index (Section 6).
We start our study about distances in a wreath product by introducing the following definition.
Notice that, for each u, v ∈ V G , the value ρ A (u, v) is a nonnegative integer, which represents the length of a solution for an instance of the TSP, where repetitions of vertices are allowed. The map ρ A is symmetric by definition, that is, , that is, if A = ∅, then ρ A coincides with the usual geodesic distance. The following lemma holds.

Lemma 4.2. For any
Proof. The union of a path from u to w visiting A, and of a path from w to v visiting B, is a path from u to v visiting A ∪ B.
In particular, we have: The following is another characterization of ρ A . We denote by Sym(n) the symmetric group on n elements.
Proof. For any path from u to v visiting the vertices a 1 , . . . , a k we define a permutation σ ∈ Sym(k) in this way: σ −1 (i) = j if a i is the j-th vertex of A visited for the first time in the path. The length of the path cannot be less than Conversely, for any permutation σ ∈ Sym(k), we construct a path that is the union of a shortest path from u to a σ(1) , with a shortest path from a σ(1) to a σ (2) , and so on. Since the length of this path is exactly , v), we have proven also the inverse inequality, and the proof is completed. Notice that in the As a corollary, we have the following bounds for ρ A in terms of the cardinality of A and of the diameter of the graph G. More precisely, we have: In particular, the lower bound is reached when A only contains vertices that appear in a shortest path between u and v; the upper bound in reached, for example, in the complete graph, as we will see in Example 4.8. The geodesic distance d G is clearly invariant under automorphism; on the other hand, for the map ρ A the situation is different, as the following proposition shows.
. Now by applying the inverse automorphism φ −1 we get the inverse inequality, and the claim follows.
We recall the following classical definitions.
Note that, if G is Hamilton-connected, then it is also a Hamiltonian graph. The viceversa is false, the cyclic graph being a simple counterexample (for a detailed analysis see Example 4.10). Moreover, all bipartite graphs are not Hamilton-connected; on the other hand, the complete graph is Hamilton-connected.
In our setting the map d Ha plays the role of a distance in some sense: we can reasonably define a notion of Hamiltonian eccentricity and Hamiltonian diameter replacing the geodesic distance d G with the map d Ha .
In particular, if a finite simple connected graph G = (V G , E G ), with |V G | = n, is Hamilton-connected, then diam Ha (G) = n and all the shortest paths starting and ending at the same vertex, visiting any other vertex, realize the Hamiltonian diameter.
Example 4.8. Let G = K n be the complete graph on n vertices (n ≥ 2). If A ⊆ V Kn , A = ∅, and u, v ∈ V Kn , then it is easy to check that: In particular, the graph K n is Hamilton-connected, and Equations (6) and (7) are verified. Moreover e Kn,Ha (u) = diam Ha (K n ) = n, for each u ∈ V Kn .
In Fig. 2, we have considered the complete graph K 6 , with a fixed labelling of the vertex set, and the subset A = {1, 2} of V K 6 . In this case, regarding ρ A as the n × n symmetric matrix such that (ρ A ) i,j = ρ A (i, j), for any i, j ∈ {1, . . . , 6}, we get:  Notice that, for A ⊆ V Pn , A = ∅, the positive integers min A and max A are vertices of P n . In order to describe ρ A , we just have to take into account that If we consider all possible cases, we have, for u ≤ v (ρ A is symmetric): In particular, for This implies that even if P n is not Hamilton-connected, the paths whose lengths realize the Hamiltonian eccentricity and Hamiltonian diameter are those starting and ending at the same vertex. In Fig. 3, we have represented the path graph P 9 and the vertex subset A = {3, 5, 6}. We have min A = 3 and max A = 6. By applying (9), or by explicitly computing the lengths of the paths, we obtain:   Let G = C n be a cycle, with n > 2. Then: Proof. As the graph C n is Hamiltonian, we have d Ha (u, u) = n, for every u ∈ V Cn (see Remark 4.6). When d Cn (u, v) = 1, so that u ∼ v in C n , then it is clear that there exists a path of length n − 1 from u to v visiting any other vertex of C n . There is no shorter path with this property, since the number of vertices to be visited is n (see lower bound in (5)).
When d Cn (u, v) > 1, the graph obtained by removing u and v has 2 connected components. Therefore a path from u to v visiting any other vertex has to visit at least twice at least one between u and v. Let be such a path. Suppose that u is visited twice (the other case being analog); then the subpath from x 1 to v is a path of length ℓ − 1 visiting any vertex of C n . Then, either d Cn (x 1 , v) = 1 and we have done, or we can iterate the same argument: a path from x 1 to v visiting any vertex of C n has to visit at least twice at least one among x 1 and v and so on. More precisely, by repeating the argument d Cn (u, v) − 1 times, we obtain a path ). Finally, we prove the thesis by noticing that there exists a good path of length exactly n − 2 + d Cn (u, v). For instance, let u * denote the neighbour of u which is closest to v: then the union of the shortest path from u to u * visiting any other vertex and the minimal path from u * to v is a path from u to v visiting any other vertex of the desired length.
As a consequence observe that, when n > 3 (and therefore we are not in the complete case), in light of Remark 4.6, the graph C n is not Hamilton-connected. More precisely, we have Recall that if we fix an ordering for the vertices of G, say V G = {x 1 , . . . , x n }, a vertex u of G ≀ H can be written as u = (y, x i ), with y ∈ (V H ) n and i ∈ {1, . . . , n}. The n-tuple y in (V H ) n can be regarded as a vertex of the n-th Cartesian power of H (see Definition 2.4). It is well known that the distance in the Cartesian product is nothing but the sum of the distances computed coordinatewise. In other words, given two vertices y = (y 1 , . . . , y n ) and y ′ = (y ′ 1 , . . . , y ′ n ) in V H ✷n , with y i , y ′ i ∈ V H for each i = 1, . . . , n, one has: Two vertices y and y ′ of V H ✷n , thanks to the ordering of V G , define a subset of V G denoted by δ(y, y ′ ) : where y = (y 1 , . . . , y n ) and y ′ = (y ′ 1 , . . . , y ′ n ).
Proof. It is easy to see that there exists a path of length d H ✷n (y, y ′ ) + ρ δ(y,y ′ ) (x, x ′ ) = n i=1 d H (y i , y ′ i ) + ρ δ(y,y ′ ) (x, x ′ ) connecting u and v. On the other hand, any path from u to v can be decomposed into the disjoint union of a path with only edges of type I and a path with only edges of type II. The first is actually a path in H ✷n from y to y ′ , and then its length has to be not less than d H ✷n (y, y ′ ). The second is a path from x to x ′ in G that must visit every vertex in δ(y, y ′ ). By Definition 4.1, its length has to be not less than ρ δ(y,y ′ ) (x, x ′ ) and the proof is done.
Remark 4.12. In the works [7,10] an analog formula is given for the word length of an element in a wreath product of finitely generated groups, via canonical form.
In the Lamplighter interpretation, in order to connect the two vertices u and v, the lamplighter has to visit each position where the colors of the lamp differ (the subset δ(y, y ′ )), starting from x, arriving at x ′ , switching the colors of the lamps at each of this position.  Proof. For every i = 1, . . . , n, let y ′ i be a vertex of V H satisfying d H (y i , y ′ i ) = e H (y i ). Set y ′ = (y ′ 1 , . . . , y ′ n ). It is clear that δ(y, y ′ ) = V G and then, if x ′ ∈ V G is a vertex such that d Ha (x, x ′ ) = e G,Ha (x), we have d G≀H ((y 1 , . . . , y n )x, (y ′ 1 , . . . , y ′ n )x ′ ) = n i=1 e H (y i ) + e G,Ha (x). Since d Ha ≥ ρ A for any A ⊆ V G (monotonicity of ρ A ), there is no vertex in V G≀H with distance from u more than d G≀H ((y ′ 1 , . . . , y ′ n )x ′ , u).

Antipodal Graph.
The notion of antipodal graph of a given graph was introduced in [31]. In [2], the antipodal of the four classical graph products, namely the Cartesian, the direct, the strong and the lexicographic product, is investigated and described in terms of the antipodal graphs of the factors. The aim of this section is to study the antipodal graph of the wreath product of two given graphs, by using the analysis performed in the first part of this section. Example 4.15. The diameter of the complete graph K n is 1 and then A(K n ) = K n . The diameter of the cycle C n is ⌊ n 2 ⌋, then the antipodal graph A(C n ) is a cycle itself if n is odd, and it is the disjoint union of the edges between opposite vertices if n is even. In formulas, we have: A(C n ) = C n n odd n 2 K 2 n even.
The diameter of the path graph P n is n − 1 and it is reached only by the pair {1, n}: the antipodal graph A(P n ) = K 2 ⊔ {n − 2 isolated vertices}, where the symbol ⊔ denotes the disjoint union.
Observe that, by Corollary 4.13, the diameter of G ≀ H depends on the diameter of H and on the Hamiltonian diameter of G. Therefore, in order to describe the antipodal graph of G ≀ H, we introduce the definition of Hamiltonian antipodal graph. Notice that, since d Ha (u, u) = 0,the Hamiltonian antipodal graph is not in general a simple graph, and loops may appear. Let us denote by O n the graph on n vertices whose edge set consists exactly of n loops, one at each vertex. In particular, this graph consists of n connected component. Moreover, for a given simple graph G = (V G , E G ), we define the (non simple) graph G   O n : the graph P n is not Hamilton-connected for n > 2, as diam Ha (P n ) = 2n − 2 = n and therefore there is no contradiction with Proposition 4.17. In the case of the cycle C n , we have: Proof. Since C 3 = K 3 , we can assume n ≥ 4. Recall that we have (see Example 4.10) diam Ha (C n ) = n − 2 + diam(C n ) = n − 2 + n 2 .
Then in the case n = 4 or n = 5 we have diam Ha (C n ) = n. By Equation (10)  In [2] it is proved that the antipodal of the Cartesian product of connected graphs is the direct product of the antipodal graphs of the factors. The following theorem is the analogue for the wreath product: the novelty consists in the fact that, in the wreath product case, the Hamiltonian antipodal of the first factor graph must be considered.
Theorem 4.19. Let G and H be two connected graphs, with |V G | = n. We have: Proof. According to Theorem 4.11 and Corollary 4.13, for any pair of vertices u = (y 1 , . . . , y n )x and v = (y ′ 1 , . . . , . . , n, and ρ δ(y,y ′ ) (x, x ′ ) = diam Ha (G). This is possible if and only if, for each i = 1, . . . , n, we have Finally, we present a characterization of connectedness for the antipodal graph of a wreath product.

Proposition 4.21. The graph A(G ≀ H) is connected if and only if A(H) and A Ha (G) are connected and A(H) is not bipartite.
Proof. It is known (see Corollary 5.10 in [21]) that the direct product of connected graphs is connected if and only if at most one of the factors is bipartite.
Example 4.22. In Fig. 4 we have represented the graph K 2 ≀ C 3 , where we have put  Two vertices are at distance 4 if and only if they share the position (x 1 or x 2 , in K 2 ) but their configurations differ in both the coordinates (0, 1 or 2, in C 3 ). By this explicit analysis, or equivalently by recalling Corollary 4.20 and remembering that A(C 3 ) = C 3 , we deduce A(K 2 ≀ C 3 ) = C 3 ×C 3 ×O 2 . The graph A(K 2 ≀ C 3 ) is depicted in Fig. 5. Observe that the direct product with O 2 is nothing but a disjoint duplication of the graph C 3 × C 3 , which coincides with the collinearity graph of the Generalized Quadrangle GQ(2, 1).  Recall from Example 4.15 that A(K n ) = K n , that for and odd n we have A(C n ) = C n , and that A(P m ) = K 2 ⊔ {m − 2 isolated vertices}. For the properties of the direct product we have, for every graphs G, G 1 , H 1 , G 2 , H 2 : Moreover, it is easy to prove that, for odd n, K 2 × C n = C 2n . By combining Theorem 4.19, Corollary 4.20, and Example 4.18, we are able to describe the antipodal graphs of several families of graphs: if m, n are odd and n ≥ 7;

Wiener index of a wreath product
The Wiener index is a distance-based topological index, introduced by H. Wiener in [34] for graphs associated with molecules. With a breadth-first search, it is possible to compute the Wiener index of an arbitrary graph with n vertices and m edges in time O(nm). However, in graphs that are products of smaller graphs, especially for the wreath product, the number of vertices and edges could be very large: a better approach, that we will use in this section, consists in relating the Wiener index of a product to the Wiener index of the factor graphs.
The Wiener index is an isomorphism invariant, that is, if G 1 and G 2 are isomorphic graphs, then W (G 1 ) = W (G 2 ). Of course, it is not a complete invariant, that is, the converse implication is false. The easiest counterexample is the pair of non-isomorphic graphs given by the cycle C 4 and the paw graph P . The paw graph is a graph with vertex set V P = {a, b, c, d} and edge E P = {{a, b}, {b, c}, {a, c}, {c, d}} (see Fig. 6). It is easy to see that W (C 4 ) = W (P ) = 8.  Figure 6. The graph C 4 and the Paw graph P .
However, it is true that, if the graph G is such that diam(G) = 2 and |V G | = n, then we have |E G | pairs of vertices at distance 1 and n(n−1) 2 − |E G | pairs of vertices at distance 2. Therefore W (G) = n(n − 1) − |E G |. This implies that two graphs of diameter 2, with the same number of vertices and the same number of edges, have the same Wiener index.
In [36] an explicit computation of the Wiener index for a Cartesian product is provided. For the sake of completeness, and in view of Theorem 5.4, we study in Lemma 5.2 the particular case of the Wiener index of a Cartesian power. Then For any pair u, v ∈ V H , the contribution given by d H (u, v) appears exactly m 2(n−1) times for each position i, and it gives: Proof. Let u = (y, x) ∈ V G≀H and u ′ = (y ′ , x ′ ) in V G≀H , with y, y ′ ∈ V H ✷n and x, x ′ ∈ V G . Then, by Theorem 4.11, we have Fixing a pair y, y ′ ∈ H ✷n , the contribution d H ✷n (y, y ′ ) appears n 2 times in the sum so that, using Lemma 5.2, we get: On the other hand, for any fixed subset A ⊆ V G , we have: as we can freely choose the n coordinates of y among the m elements of V H , and we can choose |A| coordinates of y ′ among the (m − 1) elements of V H (they have to be different from the ones chosen for y). This implies that, for every x, x ′ ∈ V G and any fixed A ⊆ V G , the contribution given by ρ A (x, x ′ ) appears m n (m − 1) |A| times in the sum, so that: Then the claim is proven according to Definition 5.3.
Notice that the coefficient of the term W ρ A (G) in Equation (11) of Theorem 5.4 only depends on the cardinality of |A|. This motivates the following definition.
The following identities hold: Proof. It follows from Theorem 5.4 and from the definition of W ρ k (G).
It follows that the vector W ρ (G) is an invariant for the graph that completely determines the Wiener index of the wreath products where G is the first factor. In other words, for any pair of connected graphs G 1 and G 2 such that W ρ (G 1 ) = W ρ (G 2 ), we have W (G 1 ≀ H) = W (G 2 ≀ H) for any connected graph H. Actually, also the converse is true, as the following proposition shows.
Proposition 5.7. For any given pair of connected graphs G 1 and G 2 , we have: Proof. It is enough to regard the term m n n k=0 (m − 1) k W ρ k (G) in (12) as a polynomial in the variable m and to use the classical fact that if the evaluations of two polynomials coincide in a number of points larger than the degree, then the two polynomials are the same. Since W (G 1 ≀ H) = W (G 2 ≀ H) for any connected graph H, in particular we have W (G 1 ≀ K i ) = W (G 2 ≀ K i ) for i = 1, 2, . . . , n + 1, and this implies W ρ (G 1 ) = W ρ (G 2 ).
It is natural to ask about the nature of this invariant.
In the remaining part of the section, we analyze the special cases of the wreath products K n ≀ H and P n ≀ H.

5.1.
Wiener index of K n ≀ H. Let us consider the case G = K n . The following lemma holds.
Lemma 5.8. The components of the Wiener vector of the complete graph K n are: Proof. Notice that, since in the complete graph K n all subsets of the same cardinality are isomorphic, the quantity W ρ A (K n ) only depends on the cardinality of the subset A. Let A ⊆ V Kn , with |A| = k ≥ 2. Then it is easy to see that Therefore, by using Equation (8) from Example 4.8 and Definition 5.3, we obtain: The claim follows.
We are now in position to prove the following theorem. Proof. By virtue of Corollary 5.6 and Lemma 5.8, we have: By the Binomial Theorem n k=0 (m − 1) k n k = m n , we deduce: Finally, by summing all the contributions, we get the claim.
Observe that Theorem 5.9 generalizes the result of [14] (case H = K m ) and of [4] (case H = C m ).

5.2.
Wiener index of P n ≀H. We know that W ρ A (P n ) = W ρ {min A,max A} (P n ) from Example 4.9. With every fixed set A, we associate the numbers and the following partition P a|b|c of the vertex set (note that a + b + c = n): whose parts have cardinality a, b, c, respectively. This induces a partition of (V Pn ) 2 into 9 parts. In the next proposition, we will give an explicit expression of W ρ A (P n ), as the sum of the contributions of each of these parts.
Proposition 5.10. Let P n be the path graph, with n > 2. Let A ⊆ V Pn and a := min A−1, b := max A − min A + 1. Then we have: More explicitly, we have:

SOME DEGREE AND DISTANCE-BASED INVARIANTS OF WREATH PRODUCTS OF GRAPHS 25
Let us denote with |O(x, n)| the sum of all entries of O(x, n). It is easy to check that (15) |O(x, n)| = (x − 1)n 2 + 1 3 (2n 3 + n).
Finally, let us denote by p n the n × n permutation matrix with 1 on the antidiagonal entries, that is, Now let ρ A be the n × n symmetric matrix such that (ρ A ) i,j = ρ A (i, j). Then 2W ρ A (P n ) = |ρ A |. The matrix ρ A consists of 9 blocks determined by the partition P a|b|c associated with A: looking at Equation (9) in Example 4.9, it can be seen that these blocks are exactly, up to rotations, the matrices introduced above: Combining this description of the matrix ρ A with Equation (17), we obtain: By a direct computation, which makes use of Equations (15) and (16), we get the claim.
We are now in position to compute the Wiener vector of the graph P n .
Proof. Once fixed three non-negative integers a, b, c such that a + b + c = n, there are exactly b−2 k−2 subsets A ⊆ {1, 2, . . . , n} with |A| = k and such that a = min Finally, by an explicit computation, we get the claim.
Notice that Theorem 5.11 presents an explicit computation of the vector W ρ (P n ). By applying the formula given in Corollary 5.6, it is possible to compute W (P n ≀ H), for every connected graph H whose Wiener index W (H) is known.

Szeged index of a wreath product
We start this section by recalling the definition of Szeged index for a connected graph G = (V G , E G ), as presented in [11]. Given an edge e = {u, v} ∈ E G (in other words, u and v are adjacent vertices in G), one defines: In particular, if d G (w, u) = d G (w, v), then w is neither in B u (e) nor in B v (e). Finally, one defines n u (e) = |B u (e)| and n v (e) = |B v (e)|. The Szeged index Sz(G) of G is defined as: It is known that, if G is a tree, then the Szeged index Sz(G) coincides with the Wiener index W (G). In [11], a more general sufficient condition for a graph G to satisfy the equality Sz(G) = W (G) is given. In [25], some connections between the Wiener index and the Szeged index are investigated, and the Szeged index of some graph compositions are described. We also want to mention that the Szeged index and a weighted generalization of it are studied for graph compositions in [28]. The aim of this section is to study the Szeged index for a wreath product of two graphs. Let G = (V G , E G ) and H = (V H , E H ) be two connected graphs. In order to compute Sz(G ≀ H) we decompose E G≀H into the subset of edges of type I, denoted by E I , and the subset of edges of type II, denoted by E II . Thus, we put so that Let us start by considering edges of type I.
Proof. By virtue of Theorem 4.11, we have: where A = δ((y 1 , . . . , y n ), (w 1 , . . . , w k−1 , a, w k+1 , . . . , w n )) and similarly B = δ((y 1 , . . . , y n ), (w 1 , . . . , w k−1 , b, w k+1 , . . . , w n )). If y k = a and y k = b, then A = B and the claim is true. If y k = a and y k = b, then 0 = d H (y k , a) < d H (y k , b) and A ⊂ B, thus ρ A ≤ ρ B by monotonicity and then d G≀H (z, u) < d G≀H (z, v): the claim is true. If y k = a and y k = b, d H (y k , a) > d H (y k , b) = 0 and B ⊂ A, thus ρ B ≤ ρ A by monotonicity and then d G≀H (z, u) > d G≀H (z, v): the claim is true. Lemma 6.4. Consider two vertices u, v ∈ V G≀H , with u = (w 1 , . . . , w k−1 , a, w k+1 , . . . , w n )x k and v = (w 1 , . . . , w k−1 , b, w k+1 , . . . , w n )x k , with a ∼ b in H. Let us put E = {u, v} ∈ E G≀H and e = {a, b} ∈ E H . Then we have: Proof. By Lemma 6.3 a vertex z = (y 1 , . . . , y n )x i ∈ V G≀H is in B u (E) if and only if y k is in B a (e). For a fixed y ∈ V H , there are exactly nm n−1 vertices z = (y 1 , . . . , y n )x i ∈ V G≀H such that y k = y, that is, |B u (E)| = nm n−1 |B a (e)|. The claim follows. Proof. By virtue of Lemma 6.4, setting z = (y 1 , . . . , y n )x i , we have: For a fixed edge e = {a, b} ∈ E H , there are exactly nm n−1 vertices z = (y 1 , . . . , y n )x i ∈ V G≀H such that y i = a, then We pass now to the investigation of edges of type II. Also in this case, the maps ρ A , with A ⊆ V G , will play a crucial role. Definition 6.6. Let G = (V G , E G ) be a connected graph, and let A ⊆ V G and e = {x j , x k } ∈ E G . We put and n x k (e, ρ A ) = |B x k (e, ρ A )|.
Lemma 6.7. Consider two vertices u, v ∈ V G≀H , u = (w, x j ) and v = (w, x k ), with w ∈ (V H ) n and x j ∼ x k in G. Let z = (y, x i ) be an arbitrary vertex of V G≀H . Then we have Proof. By virtue of Theorem 4.11, we have: The claim follows.
Then we have: Proof. By Lemma 6.7, a vertex z = (y, ρ δ(w,y) ). For a fixed x i ∈ V G , and a fixed A ⊆ V G , there are exactly (m − 1) |A| vertices z = (y, x i ) ∈ V G≀H such that A = ρ δ(w,y) . Then: Remark 6.9. The quantities n u (E) and n v (E), associated with an edge E of type II, do not depend on the configuration of the lamps: consider E = {u, v}, with u = (w, x j ), v = (w, x k ) ∈ V G≀H , and E ′ = {u ′ , v ′ }, with u ′ = (w ′ , x j ), v ′ = (w ′ , x k ) ∈ V G≀H , then n u (E) = n u ′ (E) and n v (E) = n v ′ (E). We fix w ∈ (V H ) n and set u i = (w, x i ) ∈ V G≀H , for every x i ∈ V G , and E j,k = {u j , u k } ∈ E G≀H , for every {x j , x k } ∈ E G . By virtue of Remark 6.9, we have: Finally, by combining with Lemma 6.8, we obtain By gluing together Proposition 6.5 and Proposition 6.11, and using Equation (18), we obtain the following theorem. Remark 6.13. Let H 1 and H 2 be connected graphs with |V H 1 | = |V H 2 | and Sz(H 1 ) = Sz(H 2 ). Then we have: for every graph G.
Proof. We have and then n u (e) = n u ′ (e ′ ). By exchanging the role of u and v, we get n v (e) = n v ′ (e ′ ). Remark 6.15. It follows from Lemma 6.14 that, if a graph G = (V G , E G ) is edgetransitive, then Sz(G) = |E G |n u (e)n v (e) for any e = {u, v} ∈ E G . In particular, if G is also arc-transitive, Sz(G) = |E G |n u (e) 2 , for any e = {u, v} ∈ E G . Therefore, if G and H are graphs with |V G | = n, |V H | = m, and G is edge-transitive, by Remark 6.9 we have: for any E = {u, v} ∈ E II . If G is also arc-transitive, As an application of Remark 6.15, in the following theorem we explicitly compute the Szeged index Sz(K n ≀ H), where H is any connected graph. Proof. We fix e = {x j , x k } ∈ E Kn . For any subset A ⊆ V Kn , with |A| ≥ 2, looking at Equation (8) of Example 4.8, it is easy to see that: If A = ∅, the set B x j (e, ρ ∅ ) contains only the vertex x j , so that n x j (e, ρ ∅ ) = 1. If A = {x}, then n x j (e, ρ A ) is non-zero only if x = x j : if this is the case, one has n x j (e, ρ {x j } ) = n. Notice that |{A ⊆ V G : |A| = h, x j ∈ A, x k / ∈ A}| = n − 2 h − 1 , for each h = 2, . . . , n − 1; |{A ⊆ V G : |A| = h, x j ∈ A, x k ∈ A}| = n − 2 h − 2 , for each h = 2, . . . , n.
By an explicit computation we have: Since K n is arc-transitive, by virtue of Remark 6.15, we have Sz II (K n ≀H) = m n |E Kn |n u (E) 2 , for any edge E of type II in K n ≀ H. Combining Lemma 6.8 with Equation (19), we obtain: Sz II (K n ≀ H) = 1 2 m n n(n − 1) m + (n − 1)(m − 1)m n−2 + (m − 1) 2 m n−2 2 .
Finally, combining with Proposition 6.5, we get the thesis.
Example 6.17. Consider the wreath product K 2 ≀ C 4 (see Fig. 7). According with our notation, we have n = 2 and m = 4. Moreover, as the graph K 2 is 1-regular and C 4 is 2-regular, the wreath product K 2 ≀ C 4 is a 3-regular graph on 32 vertices with 48 edges. The partition between the 32 edges of type I and the 16 edges of type II is also graphical in Fig. 7: the horizontal and vertical edges are edges of type I (representing a change of configuration, that is, a step in a copy of C 4 ), the diagonal ones are of type II (representing a change of position, that is, a step in a copy of K 2 ). There is no automorphism of K 2 ≀ C 4 sending an edge of type I to an edge of type II or viceversa (since an edge of K 2 ≀ C 4 is of type I if and only if it is contained in a 4-cycle, but any automorphism maps 4-cycles to 4-cycles). In particular, K 2 ≀ C 4 is not edge-transitive. However, by a direct computation, n u (e) = n v (e) = 16 for any edge e = {u, v} ∈ E K 2 ≀C 4 . This gives Sz(K 2 ≀ C 4 ) = e={u,v}∈E K 2 ≀C 4 n u (e)n v (e) = 16 2 |E K 2 ≀C 4 | = 12288.
Observe that this is also the value expected from Theorem 6.16, since, as we have seen in Example 6.2, one has Sz(C 4 ) = 16.