An advance in infinite graph models for the analysis of transportation networks

Int. J. Appl. Math. Comput. Sci., 2016, Vol. 26, No. 4, 855–870 DOI: 10.1515/amcs-2016-0061 AN ADVANCE IN INFINITE GRAPH MODELS FOR THE ANALYSIS OF TRANSPORTATION NETWORKS MART´ IN CERAa,∗,EUGENIO M. FEDRIANIb aDepartment of Applied Mathematics I University of Seville, ETSIA, Ctra. Utrera km 1, ES-41013 Seville, Spain e-mail: [email protected] bDepartment of Economics, Quantitative Methods and Economic History Pablo de Olavide University, Ctra. Utrera km 1, ES-41013 Seville, Spain e-mail: [email protected] This paper extends to infinite graphs the most general extremal issues, which are problems of determining the maximum number of edges of a graph not containing a given subgraph. It also relates the new results with the corresponding situations for the finite case. In particular, concepts from ‘finite’ graph theory, like the average degree and the extremal number, are generalized and computed for some specific cases. Finally, some applications of infinite graphs to the transportation of dangerous goods are presented; they involve the analysis of networks and percolation thresholds. Keywords: infinite graph, average degree, extremal problems, road transport network, percolation. 1. Introduction Graph theory is a very useful tool in various fields of human knowledge. However, when trying to solve real problems, scientists may need to develop the existing theory beyond the point it has reached so far. For instance, the analysis of continuously increasing networks, extremely complex systems, fluids filtering through porous materials, etc. requires the involvement of infinite graphs and some properties that have hitherto been developed only for the finite case. Maybe the most clear example of this fact is the average degree. In general, and not only in extremal graph theory, we can find many problems involving the relationship between the numbers of vertices and edges of a graph (see, e.g., Cera et al., 2000; 2004, Yang et al., 2002; Yousefi-Azaria et al., 2011), i.e., the average degree. In some cases, many of these problems could be posed for infinite graphs. We can find in the literature many papers studying the problem of providing a definition of the average degree for infinite graphs (see Stein, 2011; Stein and Zamora, 2013; Wierman and Naor, 2005). Up to now, no ∗Corresponding author formal definition has been found. Indeed, it is not possible to give a general definition of the average degree for any infinite graph. On the basis of the above, this paper firstly aims to relate the concepts of the infinite graph and the average degree. In fact, we define the average degree for a family of infinite graphs that we call average-measurable. This definition allows us to extend to infinite graphs the problem of determining the maximum number of edges of a graph not containinga subgraph homeomorphic to a complete graph. We study the relationship of this problem with its counterpart in finite graphs. Notation and terminology not explicitly given here can be found in theoretical handbooks (Diestel, 2000; Mader, 1998b; Milkov´a, 2009). 1.1. Function d(p)for the finite case. Given Fas a finite graph, the extremal number ex(n;F)denotes the maximum number of edges of a graph with nvertices not containing Fas a subgraph. This definition induces the most general type of question we can state in extremal graph theory. It can be posed for finite as well as infinite graphs. The question is whether some invariant (e.g., edge-density, minimum degree, chromatic number Brought to you by | Biblioteca de la Universidad de Sevilla Authenticated Download Date | 8/29/17 1:13 PM 856 M. Cera and E.M. Fedriani or average degree) has an influence on the showing up of substructures or another graph invariant. In this context, an important, well-known result in finite graph theory implies that large average degrees in finite graphs force large minors and topological minors (a subgraph homeomorphic to a complete graph) (see Diestel, 2000). The extension of these problems from finite graphs to infinite graphs is interesting in graph theory. Some of them can even be found for some extremal problems (see Stein, 2011; Stein and Zamora, 2013). Given a graph G, let us denote by v(G)=|V(G)| and e(G)=|E(G)|the cardinals of the vertices and edges of G, respectively. Then the average degree of Gis d(G)=2e(G) v(G). Now, we note that the function d(p) = inf{t:d(G)≥t−→ TKp⊆G}, stated by Mader (1967),may be formulated in terms of the function ex(n;TKp),i.e., in terms of the number of edges of a graph with nvertices and not containing a subgraph homeomorphic to a complete graph (topological clique). Proposition 1. Let pbe a non-negative integer. Then d(p)=sup n≥p2ex(n;TKp) n. Proof. Write d(n;TKp)=2ex(n;TKp) n. If d(p)>sup n≥p {d(n;TKp)}, then there exits a real number tsuch that d(p)>t>sup n≥p {d(n;TKp)}. Let us consider a graph Gsatisfying d(G)≥t> d(|V(G)|;TKp).Hence, TKp⊆Gand, therefore, by the definition of d(p),d(p)≤t, but this is not possible. Thus, d(p)≤sup n≥p {d(n;TKp)}. To prove the converse inequality, we suppose that there exists a positive integer nsuch that d(p)<d(n;TKp).Now, we consider tn∈Rsuch that d(p)<t n<d(n;TKp).Therefore, for every graph G with |V(G)|=n,ifd(G)≥tn>d(p), then (by the definition of d(p))Gcontains a subgraph homeomorphic to Kp.Hence, by the definition of d(n;TKp),we would have d(n;TKp)≤tn<d(n;TKp),but this is not possible, either. Thus, d(p)≥d(n;TKp)for all nand the result follows.  1.2. Paper objectives and structure. Bearing in mind the aforementioned result, if we want to get exact values for the function d(p),it is sufficient to calculate exact values for ex(n;TKp)with nbeing sufficiently large. In other words, since there exists a necessity of studying ex(n;TKp)for ntending to infinite, we state the problem of studying this function for infinite graphs. Additionally, the problem of studying the number of edges in relation to the number of vertices in an infinite graph has no sense. But this paper explains that it is useful as a local concept when dealing with transport networks. This fact suggests the possibility of considering the idea of defining the concept of an average degree for infinite graphs. This idea seems even more interesting if we bear in mind that an infinite graph may be considered the limit of finite graphs. Taking into account all these ideas, we note that the goal of the theoretical part of this paper is twofold. On the one hand, we define an average degree for infinite graphs inheriting the properties of the average degree for finite graphs. On the other hand, we generalize the function d(p)for finite and infinite graphs and we prove relationships between both functions. The next section deals with the generalization of the average degree for infinite graphs. The increasing concentric sequences are defined and the concept of the averagemeasurable graph is introduced. Besides, three infinite families of average-measurable graphs are presented. The following section is devoted to extending the extremal function ex(n;TKp). The function d∞(p)is defined and bounded by the corresponding‘finite version’. Some other theoretical results are proved, and they provide us with exact values for d∞(p)when 1≤p≤5. Finally, we apply the studied concepts to the transportation of dangerous goods, paying special attention to complex networks and percolation. The paper concludes with a brief summary. 2. Average-measurable graphs In this section, we define the average degree for a family of infinite graphs that we call average-measurable.We start with a sequence of finite graphs, and the average degree for infinite graphs will inherit the properties of the average degree for the finite case (see Barooah and Hespanha, 2008; Wierman and Naor, 2005; Zemanian, 1988). We are about to prove that trees are examples of average-measurable graphs. On the other hand, we introduce another family of graphs, called quasi-finite graphs, that are also proved to be average-measurable. To achieve these goals we need some notation and definitions. Definition 1. Let Gbe an infinite, locally finite graph, and let {Gn}n∈Nbe a sequence of finite subgraphs of Brought to you by | Biblioteca de la Universidad de Sevilla Authenticated Download Date | 8/29/17 1:13 PM An advance in infinite graph models for the analysis of transportation networks 857 G. We say that {Gn}n∈Nis an increasing concentric sequence (ICS) of Gif the following three conditions are satisfied: •Gn⊂Gn+1 for all n, •∂Gn∩∂Gn+1 =∅for all n, •∪ n∈NGn=G, where ∂Gn=V(Gn)−V(Gn−1)Gdenotes the boundary of Gn. We note that, given an infinite graph Gand v∈G, it is always possible to find an ICS. In fact, if we consider the subgraphs Gn(v)={u∈V(G):d(u, v)≤n}G, where d(u, v)denotes the distance between the vertices u and v, it is easy to prove that the sequence {Gn(v)}n∈N satisfies the conditions described above for being an ICS of G. Definition 2. Given an infinite, locally finite graph G, we define the inferior-average degree of Gas d∞(G) = inf lim inf n→+∞d(Gn(v)) : v∈G, where d(Gn)is the average degree of each finite graph Gn(v). On the other hand, we define the superior-average degree of Gas d∞(G)=suplim sup n→+∞ d(Gn(v)) : v∈G. Definition 3. Let Gbe an infinite, locally finite graph. Gis said to be average-measurable graph if d∞(G)=d∞(G)<+∞.Besides, in this case, we define the average degree of Gas d∞(G)=d∞(G)=d∞(G). Example 1. Let Hbe the tree shown in Fig. 1, where the vertex uis a root and the degree of the vertices of each level equals its predecessor plus one (two for the first and second levels).                                                      Fig. 1. Tree Hwith an increasing degree. If we consider the ICS {Hn(u)}n∈N,it is easy to check that, for every positive integer n, |V(Hn(u))|=2! + ···+(n+2)! 2. On the other hand, taking into account that each finite subgraph Hn(u)of H is a tree, |E(Hn(u))|=|V(Hn(u))|−1, and, therefore, lim n→+∞2·|E(Hn(u))| |V(Hn(u))|= 2 lim n→+∞1−1 |V(Hn(u))|=2. However, this property (proved for the vertex u) is, in fact, true for every vertex of H. Moreover, this property is true for every tree.  Theorem 1. Every infinite, locally finite tree Tis averagemeasurable and d∞(T)=2. The following example shows a non-average-measurable graph. Example 2. Let us consider the graph G(see Fig. 2), obtained from the graph Hin the previous example and satisfying ∂G1(v)=K3 and |E(∂Gn(v))|=n|V(Gn(v))|for n≥2.                                                                   ½     ¾            Fig. 2. Graph Gobtained from H. By induction, it is easy to see that n|V(Gn(v))|≤|V(∂Gn(v))| 2 and, therefore, it is possible to produce such a graph G. On the other hand, from the construction of G, |V(Gn(v))|=2! + ···+(n+2)! 2 and |E(Gn(v))|=|V(Gn(v))|−1+3+··· +2|V(G2(v))|+···+n|V(Gn(v))|. Now, let Mbe the graph designed in such a way that V(M)=V(H)∪V(G)∪{w} Brought to you by | Biblioteca de la Universidad de Sevilla Authenticated Download Date | 8/29/17 1:13 PM 858 M. Cera and E.M. Fedriani        Fig. 3. Graph Mobtained from Hand G. and E(M)=E(H)∪E(G)∪{(u, w),(v,w)} (see Fig. 3). We are going to study the sequences {Mn(u)}n∈N and {Mn(v)}n∈N.By the definition of Mn(u),for n≥2, |V(Mn(u))|=|V(Hn(u))|+|V(Gn−2(v))|+1 and |E(Mn(u))|=|E(Hn(u))|+|E(Gn−2(v))|+2. To determine the limit of the sequence {d(Mn(u))}n≥2, it is sufficient to analyze the behavior of the quotient |E(Mn(u))|/|V(Mn(u))|.By applying the well-known Stolz theorem for sequences |E(Mn+1(u))|−|E(Mn(u))| |V(Mn+1(u))|−|V(Mn(u))| = (n+3)! 2+(n+1)! 2+(n−1) ·2! + ···+(n+1)! 2 (n+3)! 2+(n+1)! 2 =1+ (n−1) ·2! + ···+(n+1)! 2 (n+3)! 2+(n+1)! 2 . If we apply again the Stolz theorem, we get lim n→+∞ (n−1)(2! + ···+(n+1)!) (n+3)!+(n+1)! =0. It follows that lim n→+∞2|E(Mn(u))| |V(Mn(u))|=2 and, therefore, d∞(M)≤2. Now we analyze what happens with the sequence {Mn(v)}n∈N: |V(Mn(v))|=|V(Hn−2(u))|+|V(Gn(v))|+1 and |E(Mn(v))|=|E(Hn−2(u))|+|E(Gn(v))|+2. We apply the Stolz theorem to compute the limit of the average degree of each subgraph Mn(v): |E(Mn+1(v))|−|E(Mn(v))| |V(Mn+1(v))|−|V(Mn(v))| =1+ (n+1)·2! + ···+(n+3)! 2 (n+3)! 2+(n+1)! 2 . By applying the Stolz theorem again, lim n→+∞ (n+ 1)(2! + ···+(n+3)!) (n+3)!+(n+1)! =+∞. Hence lim n→+∞2·|E(Mn(u))| |V(Mn(u))|=+∞ and, therefore, d∞(M)=+∞.Thus, d∞(M)≤2< d∞(M)=+∞, and Mis non-average-measurable.  2.1. Quasi-finite graphs. Next we define a family of infinite graphs which are average-measurable when their maximal degree is bounded. Definition 4. Let Gbe an infinite, locally finite graph. The ICS {Gn}n∈Nsatisfies the so-called boundary condition when lim n→+∞ |V(∂Gn)| |V(Gn)|=0. Remark 1. The boundary condition lim n→+∞ |V(∂Gn)| |V(Gn)|=0 is equivalent to lim n→+∞ |V(Gn−1)| |V(Gn)|=1, since |V(∂Gn)| |V(Gn)|=|V(Gn)|−|V(Gn−1)| |V(Gn)| =1−|V(Gn−1)| |V(Gn)|. Definition 5. Let Gbe an infinite, locally finite graph. G is said to be quasi-finite if there exists a vertex v∈Gsuch that the ICS {Gn(v)}n∈Nsatisfies the boundarycondition. The following result shows that the previous definition does not depend on the chosen vertex, i.e., if there exists a vertex vfor which {Gn(v)}n∈Nsatisfies the boundary condition, then it is satisfied for all v. Brought to you by | Biblioteca de la Universidad de Sevilla Authenticated Download Date | 8/29/17 1:13 PM An advance in infinite graph models for the analysis of transportation networks 859 Lemma 1. Let Gbe an infinite, locally finite graph. If Gis quasi-finite, then the sequence {Gn(v)}n∈Nsatisfies the boundary condition for all v∈G, i.e., lim n→+∞ |V(∂Gn(v))| |V(Gn(v))|=0. Proof. Let Gbe a quasi-finite graph and v0beavertex such that the ICS {Gn(v0)}n∈Nsatisfies the boundary condition. Given v∈G, we denote by rthe distance between vand v0(r=d(v,v0)). Taking into account Remark 1, it is sufficient to prove the equality lim n→+∞ |V(Gn−1(v))| |V(Gn(v))|=1 to show that the boundary condition is satisfies. Consequently, we note that, for n≥r+1, Gn−r−1(v0)⊆Gn−1(v), Gn(v)⊆Gn+r(v0). Hence |V(Gn−1(v))| |V(Gn(v))|≥|V(Gn−r−1(v0))| |V(Gn+r(v0))|. Furthermore, |V(Gn−r−1(v0))| |V(Gn+r(v0))| =|V(Gn−r−1(v0))| |V(Gn−r(v0))| |V(Gn−r(v0))| |V(Gn−r+1(v0))| ···|V(Gn+r−1(v0))| |V(Gn+r(v0))|, but |V(Gn−r−1(v0))| |V(Gn−r(v0))| −−−−→ n→+∞1 . . . |V(Gn+r−1(v0))| |V(Gn+r(v0))| −−−−→ n→+∞1. Finally, 1≥lim n→+∞ |V(Gn−1(v))| |V(Gn(v))| ≥lim n→+∞ |V(Gn−r−1(v0))| |V(Gn+r(v0))|=1. Thus, lim n→+∞ |V(Gn−1(v))| |V(Gn(v))|=1, and the result follows.  Remark 2. By reasoning as in Lemma 1, we get lim n→+∞ |V(Gn(v))| |V(Gn+k(v))|=1 for all positive integer k. The previous lemma can be generalized to other sequences. In fact, given a finite G0⊂G, we consider the ICS {Gn(G0)}n≥0as the sequence defined as follows: Gn(G0)={u∈V(G):d(u, G0)≤n}G. Theorem 2. Let Gbe an infinite, locally finite graph. Then Gis quasi-finite if and only if there exists a finite subgraph G0⊂Gsatisfying the boundary condition, that is to say, lim n→+∞ |V(∂Gn(G0))| |V(Gn(G0))|=0. Besides, if the aforementioned assertion is true, then the boundary condition is satisfied for every finite subgraph G0⊂G. Proof. Let Gbe an infinite, quasi-finite graph, and G0⊂ Gbe a finite subgraph. We are proving that lim n→+∞ |V(Gn−1(G0))| |V(Gn(G0))|=1. For this purpose, let us consider v0∈V(G0)and denote by rthe diameter of G0(r=diam(G0)). Consequently, Gn−1(v0)⊆Gn−1(G0) Gn(G0)⊆Gn+r(v0) for all n. It follows that |V(Gn−1(G0))| |V(Gn(G0))|≥|V(Gn−1(v0))| |V(Gn+r(v0))|. Bearing in mind the inequality |V(Gn−1(G0))| |V(Gn(G0))|≤1 and by applying Remark 2, 1≥lim n→+∞ |V(Gn−1(G0))| |V(Gn(G0))| ≥lim n→+∞ |V(Gn−1(v0))| |V(Gn+r(v0))|=1. Therefore, lim n→+∞ |V(Gn−1(G0))| |V(Gn(G0))|=1. In order to prove the converse implication, we suppose that there exists a G0such that the sequence {Gn(G0)}satisfies the boundary condition. Since that v0∈V(G0)and r=diam(G0), Gn−r−1(G0)⊆Gn−1(v0) and Gn(v0)⊆Gn(G0). Brought to you by | Biblioteca de la Universidad de Sevilla Authenticated Download Date | 8/29/17 1:13 PM 860 M. Cera and E.M. Fedriani Hence |V(Gn−1(v0))| |V(Gn(v0))|≥|V(Gn−r−1(G0))| |V(Gn(v0))|. By reasoning as in Remark 2, we see that lim n→+∞ |V(Gn−r−1(G0))| |V(Gn(G0))|=1, so that lim n→+∞ |V(Gn−1(v0))| |V(Gn(v0))|=1.  Now, we are going to prove that every quasi-finite graph with a bounded maximal degree is average-measurable. Theorem 3. Let Gbe an infinite, locally finite graph with Δ(G)<+∞.If Gis quasi-finite, then Gis averagemeasurable. Proof. Let Gbe an infinite graph with maximal degree Δ(G)=Δ<+∞.Given v∈G, we consider the sequence Gn=Gn(v)for n∈N.Since Δ(G)<+∞, we know that d(Gn)≤2Δ.To prove that {d(Gn)}is convergent,we check that, in fact, it is a Cauchy sequence, that is, lim n→+∞|d(Gn+1)−d(Gn)|=0. Now, we consider the sequence {sn}defined as follows: sn= |E(Gn+1)| |V(Gn+1)|−|E(Gn)| |V(Gn)| = |E(Gn+1)|·|V(Gn)|−|E(Gn)|·|V(Gn+1)| |V(Gn)|·|V(Gn+1)| . If we set E(∂Gn,∂G n+1)={(wn,w n+1)∈E(G): wn∈∂Gn,w n+1 ∈∂Gn+1}, then (see Fig. 4) |E(Gn+1)|=|E(Gn)|+|E(∂Gn,∂G n+1)| +|E(∂Gn+1)|. Thus, sn= 1 |V(Gn)|·|V(Gn+1)| |V(Gn)||E(Gn)|+|E(∂Gn,∂G n+1)| +|E(∂Gn+1)|−···−|E(Gn)|·|V(Gn+1)| ≤|E(Gn)|||V(Gn)|−|V(Gn+1)|| |V(Gn)|·|V(Gn+1)| +|E(∂Gn,∂G n+1)| |V(Gn+1)|+···+|E(∂Gn+1)| |V(Gn+1)|.  wn  wn+1 Gn ∂Gn ∂Gn+1 Fig. 4. Edge decomposition E(Gn+1). However, |E(Gn)|||V(Gn)|−|V(Gn+1)|| |V(Gn)|·|V(Gn+1)|≤Δ·|V(∂Gn+1)| |V(Gn+1)|, |E(∂Gn,∂G n+1)| |V(Gn+1)|≤Δ·|V(∂Gn)| |V(Gn+1)|≤Δ·|V(∂Gn)| |V(Gn)|, and |E(∂Gn+1)| |V(Gn+1)|≤Δ·|V(∂Gn+1)| |V(Gn+1)|. Hence sn≤Δ·|V(∂Gn+1)| |V(Gn+1)|+Δ·|V(∂Gn)| |V(Gn)| +Δ·|V(∂Gn+1)| |V(Gn+1)|. As lim n→+∞ |V(∂Gn)| |V(Gn|=0, we get lim n→+∞sn=0 and, therefore, the sequence {d(Gn)}n∈Nis convergent. Finally, to reach d∞(G)=d∞(G),we are going to prove that, for all u∈V(G), lim n→+∞ |E(Gn(u))| |V(Gn(u)|= lim n→+∞ |E(Gn(v))| |V(Gn(v)|=t. For this purpose, we consider u∈V(G)and r=dG(u, v).Accordingly, tn = |E(Gn(u))| |V(Gn(u))|−|E(Gn(v)| |V(Gn(v)| = |E(Gn(u))||V(Gn(v))|−|E(Gn(v))||V(Gn(u))| |V(Gn(u))||V(Gn(v))| . Besides, taking into account that Gn−r(v)⊆Gn(u)⊆Gn+r(v) Brought to you by | Biblioteca de la Universidad de Sevilla Authenticated Download Date | 8/29/17 1:13 PM An advance in infinite graph models for the analysis of transportation networks 861 for n≥r, we have that tn≤ 1 |V(Gn−r(v))||V(Gn(v))| ×(|E(Gn+r(v))||V(Gn(v))| −|E(Gn(v))||V(Gn−r(v))|) × |E(Gn+r(v))| |V(Gn−r(v))|−|E(Gn(v))| |V(Gn(v))| . Since lim n→+∞ |V(Gn(v))| |V(Gn+1(v))|=1 and |E(Gn+r(v))| |V(Gn−r(v))|=|E(Gn+r(v))| |V(Gn+r(v))| |V(Gn+r(v))| |V(Gn+r−1(v))| ×|V(Gn−r+1(v))| |V(Gn−r(v))|, we conclude that lim n→+∞ |E(Gn+r(v))| |V(Gn−r(v))|=t and, therefore, lim n→+∞tn=0. Now, we note that the condition Δ(G)<+∞is necessary in this theorem, as we can see with the graph G from Fig. 5: Gis quasi-finite but not average-measurable.                  Æ    Æ    Æ       Æ       ½  ¾  ¿    Fig. 5. Quasi-finite graph with Δ(G)=+∞, but non-averagemeasurable. This graph is defined in such a way that the subgraph ∂Gnis a complete graph of size 2n+1,for n≥1.Thus, |V(Gn(v))|=1+3+5+···+(2n+1) and |E(Gn(v))|=3+5+···+(2n+1) +3 2+5 2+··· +2n+1 2. Gis quasi-finite because lim n→+∞ |V(∂Gn(v))| |V(Gn(v))| = lim n→+∞ 2n+1 1+3+5+···+(2n+1) =0. In order to get the limit of |E(Gn(v))|/|V(Gn(v))|,we apply the Stolz theorem: |E(Gn+1(v))|−|E(Gn(v))| |V(Gn+1(v))|−|V(Gn(v))| =2n+3+2n+3 2 2n+3 =+∞. Thus, d∞(G)=+∞and Gis not average-measurable. On the other hand, we consider the graph Hfrom Example1tofindanaverage-measurable graph which is not quasi-finite. Actually, since His a tree, this graph is average-measurable; however, it is not quasi-finite: |V(∂Hn(u))| |V(Hn(u))|=|V(Hn(u))|−|V(Hn−1(u))| |V(Hn(u))| =(n+2)! 2! + ···+(n+2)!. By applying the Stolz theorem, lim n→+∞ (n+3)!−(n+2)! (n+3)! = lim n→+∞ n+2 n+3 =1=0 and, therefore, the sequence {Hn(u)}does not satisfy the boundary condition, and hence His not quasi-finite. 2.2. Periodic graphs. Now, we are going to show that periodic graphs are quasi-finite. These graphs are very useful because they are frequent and easily computed. We can find examples of periodic graphs in tiling and patterns (Gr¨unbaum and Shephard, 1987) or Cayley diagrams (Cayley, 1895; Frucht, 1938), and they even appear as the resultant graphs of solving linear systems (Bauderon, 1989). Here we recall some prior results on periodic graphs. We denote by Cthe unit square [0,1] ×[0,1] ⊂R2,and we define a cellular graph as the graph satisfying V(G)⊂ Cwith no isolated vertices. Thus, given a cellular graph G, we define the 2-dimensional periodic graph (MG)as the graph obtained from Gas follows: V(MG)=τ(m,n)(v):v∈V(G)and (m, n)∈Z2, E(MG)=(τ(m,n)(u),τ (m,n)(v)) : (u, v)∈E(G)and (m, n)∈Z2, Brought to you by | Biblioteca de la Universidad de Sevilla Authenticated Download Date | 8/29/17 1:13 PM 862 M. Cera and E.M. Fedriani where τ(m,n)denotes the translation by vector (m, n)in the plane. If MGis a 2-periodic graph generated by the cellular graph G, then we define the 8-neighbors of Gas the subgraphs τ(i,j)(G)of MGsuch that i∈{−1,0,1}and j∈ {−1,0,1}, with (i, j)=(0,0). Given a cellular graph Gand the 2-periodic graph generated by G, MG,we define the n-square of center G and radius n(nG) as the subgraph of MG: nG=τ(i,j)(G):(i, j)∈Z2,max{|i|,|j|}≤n. We are proving that, in fact, the 2-periodic graphs are quasi-finite and average-measurable (since they have a bounded maximal degree). Theorem 4. Every infinite, periodic, connected graph MGgenerated by the cellular graph Gis quasi-finite and average-measurable. Proof. Let Gbe a cellular graph and M=MGbe the 2-periodic graph generated from G. By Theorem 2, it is sufficient to prove that lim n→+∞ |V(∂Mn(G))| |V(Mn(G))|=0 to show that Mis quasi-finite. We recall that Mn(G)=u∈V(M):d(u, G)M≤nM. Consider d=max{d(u, G):u∈Gi,1≤i≤8}, where Giare the 8-neighbors of G. Firstly, for all n≥d, it is easily seen that (see Fig. 6) n dG⊆M n(G)⊆nG, because if v∈n dG, then (see Fig. 7) d(u, G)≤d+d(u, n d−1G)≤···≤dn d≤n. Accordingly, |V(∂Mn(G))| |V(Mn(G))| ≤|V(∂Mn(G))| |V(n dG)|≤|V(∂Mn(G))| 2n d+1 2|V(G)| . On the other hand, for all n≥1,let us consider k(n)=|V(∂Mn(G))|.As V(Mn(G)) = n  i=0 V(∂Mi(G)) ⊆V(nG),                                                 ½          Fig. 6. Chain of inclusions for Mn(G).                                ½  Fig. 7. n dG⊆M n(G). we have sn=k(1) + k(2) + ···+k(n)≤(2n+1) 2|V(G)|. Suppose that lim sup n→+∞ k(n) n2=l, with l>0.By applying the Stolz theorem to the quotient sn/(2n+1) 2,we get that sn+1 −sn (2n+3) 2−(2n+1) 2=k(n+1) 8n+9 =k(n+1) (n+1) 2 (n+1) 2 8n+9 and, therefore, lim sup n→+∞ sn (2n+1) 2|V(G)| =1 |V(G)|lim sup n→+∞ k(n+1) (n+1) 2 (n+1) 2 8n+9 =+∞. Brought to you by | Biblioteca de la Universidad de Sevilla Authenticated Download Date | 8/29/17 1:13 PM An advance in infinite graph models for the analysis of transportation networks 863 But this is not possible, because we were assuming that sn (2n+1) 2|V(G)|≤1. Consequently, lim n→+∞ k(n) n2=0 and, therefore, lim n→+∞ |V(∂Mn(G))| 2n d+1 2|V(G)| ≤1 |V(G)|lim n→+∞ k(n) n2 n2 2n d−1+1 2=0. Thus lim n→+∞ |V(∂Mn(G))| |V(Mn(G))|=0 and Mis quasi-finite. Besides, since Mis a 2-periodic graph, the assertion Δ(M)<+∞is satisfied, and (by applying Theorem 3) Mis average-measurable.  Now, we present an illustration of a 2-periodic graph. Example 3. We consider the 2-periodic graph M generated by the cellular graph Gas in Fig. 8.                                                                                                                                                                                                         Fig. 8. Periodic graph with the average degree 8 3. Since Mis connected, by applying Theorem 4, we deduce that this graph is average-measurable. Let us consider the sequence {Mn(G)}.Since the sequence {d(Mn(G))}is convergent, we know that lim n→+∞d(Mn(G)) = lim n→+∞d(M2n(G)). On the other hand, |V(M2n(G))|=5+16+6(4+8+···+2 n) and |E(M2n(G))|=4+16+8(4+8+···+2 n) and, therefore, by applying Stolz Theorem, lim n→+∞d(M2n(G)) = 8 3.  Remark 3. In interconnection networks, it is important to control their behavior when edges are subdivided or contracted. Taking into account the definition of an average degree for infinite graphs that we have just introduced, it is straightforward to check that if we subdivide one or more edges in a graph, the average degree of the resulting graph is less than or equal to the original. In the following example (Fig. 9), it is easy to check that the average degree is four. If subdivisions of each edge are performed (Figure 10), we obtain a graph with a smaller average degree (the one shown in Fig. 8). Fig. 9. Periodic graph with the average degree 4. Fig. 10. Periodic graph with the average degree 8 3. In the graph displayed in Fig. 11 we can observe the behavior of the average degree when performing contractions of edges. Another kind of periodic graph is the 1-dimensional case. This graph M1 Gis generated by a cellular graph G and horizontaltranslationsGiof the graph G(see Fig. 13). Here we denote by vithe translated vertex of vin Gi,for all integers iand all v∈V(G). Now, we are able to formulate a general result. Theorem 5. Let Gbe a finite cellular graph. If M1 Gis connected, then it is quasi-finite and, therefore, averagemeasurable. Brought to you by | Biblioteca de la Universidad de Sevilla Authenticated Download Date | 8/29/17 1:13 PM