Discrete operators and distances on subdivision networks

x2n x1 x2 x3 x4 x5 x0 x0 2n x0 2 x0 4 Discrete operators and distances on subdivision networks Enric Monsó Burgués Thesis Advisors Ángeles Carmona and Margarida Mitjana Universitat Politècnica de Catalunya, 2022 DISCRETE OPERATORS AND DISTANCES ON SUBDIVISION NETWORKS Enric Monsó Burgués A Thesis submitted for the degree of Doctor of Mathematics in the Universitat Politècnica de Catalunya Thesis Advisors Ángeles Carmona and Margarida Mitjana Doctoral Program APPLIED MATHEMATICS Barcelona, June 2022 Facultat de Matemàtiques i Estadística Enric Monsó Burgués Departament de Matemàtiques Universitat Politècnica de Catalunya Terrasa Barcelona [email protected] Agraïments A tots els que he tingut la sort de conéixer, als que citaré i a tants d’altres que oblidaré citar...Gràcies. Sempre he pensat que a la vida hi havia un moment adequat per a cada cosa. I per a mi el moment de fer una tesi doctoral ja feia molt temps que havia passat. Però com és habitual, m’equivoco... I en aquestes que van aparéixer l’Andrés i les seves dones, l’Ángeles, la Margarida, la Maria José i, en aquells moments també la Sílvia. I em vaig deixar convéncer, gràcies MJ. I vaig fer santament. Perqué treballar amb aquest grup de persones ha significat un renaixement total. I ja els ho he explicat moltes vegades, però ara tinc ganes d’escriure– ho aquí. I de remarcar–ho. Perqué és clar que matemàticament són molt competents i és clar que treballen en un àmbit molt interessant, però pel que a mi, el que jo més valoro és que són persones. I per això, en aquests moments de felicitat, he d’agrair al grup (ara amb l’Àlvar també) l’escalf, l’impuls, l’estima que m’heu feu sentir. I mira que no he estat fàcil. Però afortunadament per mi sou més tossudes vosaltres que no pas jo. Gràcies. I sobretot gràcies a les meves dues fantàstiques directores. A l’Ángeles, que m’has adoptat com si fós un altre Héctor i m’has demostrat un gran cor, una tendresa que no esperava i una infinita paciència. I a la Margot, que ets tan entranyable i bona gent, i que també m’has tingut una paciència infinita. Sé que us he fet patir, segurament més a la Margot, que és tan endreçada i competent. I em sap greu, i m’agradaria disculpar-me. Però finalment tot ha sortit bé. Quina sort tenen els vostres de tenir-vos, i quina sort he tingut jo també. Felicitats a les dues. Pel que sembla ho heu aconseguit. Però és que es tracta del grup MAPTHE. I al capdavant l’Andrés, un pou de coneixement però sobretot una disposició infinita. Probablement la persona més noble que he conegut. I la Maria José, que és qui va aconseguir que fes cas a aquest estol d’estrelles. I que també estàs per al que faci falta, 4 i s’agraeix. I finalment, per ordre cronològic, l’Àlvar, a qui potser sabré retornar una mica d’allò que els altres tan sàviament m’han fet arribar. Com que sóc tot un borinot, no sabré trobar les paraules justes. De ben segur, com succeeix habitualment, que em sabreu disculpar. I també vull recordar els companys que he tingut i tinc a l’Escola, a Terrassa. Els que m’han ajudat a ser qui sóc, amb tots els ets i tots els uts. I ara vull recordar en Santi, qui també em va saber acollir i a qui reconec una gran ascedència. I també en Víctor, un altre home del renaixement, a qui tant aprecio. I en aquest moment d’eufòria, vull tenir un record i un agraïment per la meva família Monsó. Us reconec la vostra contribució en qui sóc. Als pares, el pare i la mare, als que tot ho dec i als que també he fet patir. Als qui a vegades he escoltat i a vegades no, a qui en algunes ocasions crec haver enorgullit i altres vegades... I als meus germans, l’Albert i la Mònica. I també vull aprofitar per citar la meva família Mas, a tots ells, tant en una altra òrbita, i de qui també he aprés tantes coses. I també recordo amb tendresa l’abuela... Però sobretot tinc un especial deute amb les meves tres princeses. A elles tres vull agraïr particularment ser el seu bufó. Perqué trobo que us estimo tant que a vegades riem, i també us estimo tant que a vegades cridem. Marina i Helena, belles. Generoses. Capaces. Sou la meva inspiració i estic tant satisfet en pensar que potser he contribuït mínimament al que sou, que ja em sento ben pagat. Només espero que el dia de demà reconeixereu que us estimo tant. I finalment la Marina. Disculpeu tots els altres, però aquesta sí que ho és tot per mi. Honestament no sé què en seria de mi, si no m’hagués volgut al seu costat, si no m’hagués dit que sí, a mi! aquell bell dia quan li ho vaig demanar. Sense els seus apunts no seria..., sense els seus consells no seria..., sense el seu exemple no seria... Sense la Marina vés a saber qui seria. Estic molt agraït a la vida d’haver–te conegut. Sempre recordaré el primer dia que et vaig veure...des d’aleshores que em declaro presoner teu. I per sempre. No sé pas què vas veure en mi que els altres no veuen, però ho celebro. I t’estimo! Sant Cugat del Vallès, juliol 2022. 1 Abstract The aim of the work we have developed is to contribute to the understanding of discrete elliptic boundary value problems on finite networks from an electrical point of view as we are concerned with a particular operation on networks that has a physical meaning in circuit theory. Elliptic problems in the continuous field are a very well known item in physical mathematics. It is a very important tool in the development of so many situations of real interest and many efforts have been devoted to it from a long time ago. Even though our work is centered in the discrete field, we use notations that are inspired in the continuous setting for elliptic operators because there is a strong symbiosis between both fields. Indeed, sometimes solving a problem in the discrete setting can lead to the solution of its continuum version by a limit process, but sometimes the relation between these two worlds does not work so easily. It is very clear that an electrical network may be viewed as a graph, and conversely, that every graph can be considered as a model of an electrical circuit, after considering that electrical components are identified with vertices and the interconnections between electrical components are described as edges. In other words, electrical circuits are naturally treated as graphs. When some item is connected to a circuit, an straightforward interpretation is to add one or various vertices to the former graph and/or consider new information defined on the edges of the graph. We are interested not only in graphs, discrete structures where vertices and nodes are considered all equal (only the number of incident edges to an specific vertex make a difference between different vertices), but in networks that are discrete structures where edges are equipped with a conductance (a positive value) that discriminates edges from other edges and is also possible to consider a value for every vertex that differentiate vertices among them (even further than for the adjacencies). An elementary subdivision of a nonempty network is not electrically compatible as, when inserting a vertex in an edge, does not satisfy the total resistance series connection electrical law. We are interested in the subdivision 6 Chapter 1. Abstract procedure on networks so as to model the physical situation of connecting items (to all edges or only to some of the edges) to an electrical network. These connections have to be electrically compatible and the concept of conductance associated with every edge has to satisfy the requirement of 1 c(x, y)=1 c(x, vxy)+1 c(vxy, y) where x, y are vertices on the network, vxy is the new vertex inserted in the edge {x, y}after the elementary subdivision procedure, {x, vxy}and {vxy, y}are the resulting two new edges and provided that a conductance is the inverse value of a resistance. In this way the very well known physical law for electrical resistance in a series connection is satisfied. All along our work we have considered global subdivision procedures first and a partial subdivision procedure of only some edges later, as this case is a more general one. We will continue our future work with an even more general subdivision operation where just some edges should be replaced by different length open paths. Thus our task has consisted in stating the precise connection between solutions of elliptic problems on these related discrete structures, a given initial network and another one resulting of a subdivision procedure of the former. Moreover, and again from the existing relationship between discrete structures and electrical circuits, a novel distance concept was introduced by exploiting the idea that, given an edge and its two adjacent vertices, the more the resistance value of and edge is, the further both adjacent vertices are. This so called resistance distance is proved to be thinner than the canonical shortest–path distance that is usually considered in graph theory but, what is more important to us, is suitable to treat diffusion problems on discrete structures as in most cases spreads try every single possibility of propagation at their hand and this distance is defined between two different vertices taking into account all possible paths that join them. Furthermore, very important topological information of the structure we are interested in is easily obtainable upon this resistance distance concept. More specifically, we are focussed in determining the existing relationship between resistance distances and also between Kirchhoff indexes of these discrete structures, relating those parameters of the subdivided structures with their respective of the given initial structure. In order to compute resistance distances, we take advantage of the so called Green’s kernel of an elliptic operator. First for the Laplacian operator, then for Schödinger type operators, we have studied how to relate Green’s kernel function for the subdivided network in terms of Green’s kernel of the former discrete structure. As there exists a one-to-one identification between electrical circuits (graphs, networks) and M–matrices, and given that Green’s 7 kernel of an elliptic operator is also identified with the Moore–Penrose inverse matrix, our problem can also be seen as a contribution to the computation of higher dimensional Moore–Penrose inverse matrices in terms of given lower order Moore–Penrose inverse matrices in a sort of Woodbury–Shermann– Morrison formula, a well known result but for singular matrices. 14 Chapter 2. Introduction the graph. Also in [71] an expression for the Kirchhoff index in terms of a {1}–inverse of the combinatorial Laplacian is given. Also, subdivision graphs and their spectra seem to be particularly important in the study of thermodynamic properties of crystalline solids. This practical problem led B.E. Eichinger and J.E. Martin in [41], to devise an algorithm for computing the Laplacian eigenvalues of a subdivided graph by applying numerical linear algebraic methods to the matrix of the unsubdivided graph. But none of these works seem to realize the existence of the obvious coincidence we have mention in the initial paragraph of this introduction. As far as we know nobody has used graph subdivision to model series connection in an electrical circuit. On the other hand complex systems are pervasive in our society. Everybody knows so many examples that support the previous sentence (the Internet System, the World Wide Web System, the electrical power system, any biological system, .. .). Possibly there are three main aspects to have in mind to study complex systems: the nature of the individual components of the systems, the nature of connections or interactions and the pattern of connections between components. And it is at these points where graphs should be equipped, for well modelling really interesting situations, with alternatives that allow the discrimination between vertices (per se and not just because every vertex has its own quantity of adjacent edges), and between edges (as different links may have different behaviours). Then a third actor has a role in the play, as networks should be a too simple tool to face the study of the dynamical behavior of an aggregation of nodes and links. In our vocabulary it is called Schrödinger type operators as a potential function is defined over the vertices of the structure, so as the particular value it attains at every single node may model a specific behaviour. The nodes, for vertices, might be molecules or genes for biological systems, humans for social systems, routers or switches for communication systems, transformers for electrical systems. The links, for edges, might be contagions or synapses for biological system, friendships or other relationships for social systems, physical wires or wireless for communication systems, connections for electrical systems, etc. And the behaviour of whatever is defined on the structure (not the structure itself) is the third component to take into account in a serious analysis of a real problem. Is in this direction, over the years, that scientists have developed a huge set of mathematical, computational, and statistical tools for analyzing, modeling and understanding networks. These tools work with networks in their abstract form and help in finding some crucial and useful information about them, for example, the critical node or edge in a network, the length of a 15 path from one node to another in a network, the flow of traffic over the network, clusters or communities in a network, etc. These tools can be applied to any systems that can be represented as networks. And we honestly think that the techniques of discrete potential theory applied in this setting, mimicking the theory of partial differential equations in the continuous case, can be considered as a modest contribution to this amount of knowledge. And our work in this thesis follows this line, as we have been concerned with the study of Poisson problems on discrete structures having in mind diffusion contexts as the spread of an epidemic, heat transfer or whatever that flows throughout the set of vertices and edges is distributed. Some authors, for instance [44], support the idea that it is more important to understand the organizational principles of such systems on the basis of their connectivity than to understand the role of their individual components. And it is in this sense that discrete Laplacian–like operators appear in the mathematical description of the majority of dynamical processes occurring on these systems, becoming more and more popular from time to time but unfortunately at still low levels. A third very profitable idea that we would like to expose at this particular moment is that an efficient way to get valuable information from a graph or a network is to associate the discrete structure with matrices. Then some characteristics of these matrices have a direct translation in terms of relevant information concerned with the discrete structure. When finite graphs are considered, these matrices can be related to kernels of linear operators that are defined on the vertex set, so as acting on the discrete structure. For instance, a Laplacian matrix associated with the Laplacian operator can be seen as an object that acts distributing whatever is considered throughout the network, in a so called diffusion problem. There are quite a few very well known matrices commonly tied with graphs and networks, whose consideration has returned in a profit on the knowledge of discrete structures. The probably most basic one is the so called adjacency matrix, from what important properties of a graph can be revealed such as the order of the structure, the count of paths of a precise length in the graph, the number of clicks that exist or whether the graph is bipartite or not. Also the Laplacian matrix is widely used for counting the number of spanning trees, studying connectivity, counting the number of connected components and more. The normalized Laplacian matrix, see [33] is also a very well known matrix that has been shown to be adequate enough to analyze from a probabilistic point of view a discrete structure. The normalized Laplacian discriminates vertices not only by the connections established with other vertices, but also considering the different behaviour that the corresponding edges can have. Nevertheless it is not able to capture an intrinsic discrimination of the vertices between them beyond for connections. 16 Chapter 2. Introduction A fourth argument, to include and briefly discuss in this not at all short introduction, is a sort of geometrical and topological one. For decades to know what a graph looks like has been a main objective. So, new tools have been developed so as to understand networks from some other points of view. In this sense, Klein and Randić in [58] but also Stephenson and Zellen in [70] introduced both, independently, with no apparent connection and from two very separate frameworks, a new distance function that we call resistance distance. The electrical version of it, based on electric network theory, is defined to be the effective electrical resistance between two vertices when each edge is replaced by a unit resistor. But the social networks version of the same distance, see [18, 37] where the equivalence is stated, insists in the interesting and profitable idea that distances in a discrete structure that are based upon consideration of all possible paths between two given vertices do worth a value. From this point of view, vertices in the discrete structure are closer (this distance is thinner than the canonical shortest–path distance) but, what is more important to us, the resistance distance reacts to changes in the overall structure, whether they are due to erased/incorporated edges, or a variation of the modelled behaviour. So, this new exciting context fits extremely well with the initial idea of our work. Moreover, once a new distance is considered, new topological invariants can be defined and studied. And paradoxically some valuable ideas initially developed in a Chemistry theory framework, as for instance the Wiener index, can be reproduced in some other very different frameworks as electrical circuits, thermodynamics, random walks, general science networks or others. Thus, based upon this resistance distance, the Kirchhoff index, that can be defined as the sum of resistance distances between all pairs of vertices of the network, is a classifier which is worth computing and studying. Not surprisingly, the different considerations that have been presented in this introduction of course can be intimately related. For example the calculation of resistance distances, and therefore of Kirchhoff indexes, is related to the Moore–Penrose inverse matrix of the Laplacian matrix associated with a network where a diffusion problem is posed. And in this context is where our work has to be interpreted and comprehended. Moreover, despite the great interest generated by resistance distances and Kirchhoff index, and the obvious importance of diffusion problems modelled by operators as those we consider and the subdivision procedure, we have taken no profit at all of the published literature in relation with these, our concerns. Certainly, there are some works that point in this direction, in [22] the authors investigated resistance distance in subdivision–vertex join and subdivision–edge join of graphs, also in [61] the resistance distance and Kirchhoff index of R–vertex join and R–edge join of two graphs are given, in [78] the Kirchhoff index of some composite operations between two graphs such as product, lexicographic product, join, corona and cluster is considered. 17 For sure that in [49] the Kirchhoff index for graphs derived from a single graph is studied. But all literature, as far as we know, is only concerned with graphs. So, the opportunity of considering really interesting discrete structures is missed. Or to put in other words, the knowledge more or less related to a subdivision procedure and resistance distances is devoted just to the simple graph setting, with no possibility of satisfying the electrical compatibility condition that we are interested in. Therefore, we have faced a completely exciting new paradigm: we have studied different diffusion problems (for different difference operators), resistance distances and Kirchhoff index in a setting of more sophisticated discrete structures and by applying the subdivision operation but with an electrical compatibility condition to fulfill. Once we have explained the motivations and introduced our work, we point out that we have four research papers that are already published. One of these in an online journal (ENDM) and the other three on paper support classical very reputated journals in the scope of our work (LAMA and AAMD), both usually in the highest Q1 range. Next we give their references in chronological order of appearance and a very short explanation of the realized work. 1. Á. Carmona, M. Mitjana and E. Monsó. The group inverse of subdivision networks Electronic notes in discrete mathematics,54: 295–300, 2016. url = http://hdl.handle.net/2117/101529 doi = 10.1016/j.endm.2016.09.051 This first work to appear, in an online publication, is related to what we expose in this memory as our second case, since the normalized Laplacian operator on a subdivision network was treated there. It is a work written in a matrix scenario rather than our prototypical functional framework. 2. Á. Carmona, M. Mitjana and E. Monsó. Effective resistances and Kirchhoff index in subdivision networks. Linear and Multilinear Algebra,65: 1823–1837, 2017. https://doi.org/10.1080/03081087.2016.1256945 In second place we obtained the publication of our first work, where we studied total electrical compatible subdivision of networks and the Laplacian operator was considered. The definition of resistance distance is the classical one, as in [58]. 18 Chapter 2. Introduction 3. Á. Carmona, M. Mitjana and E. Monsó. Green’s function in partial subdivision networks. Linear and Multilinear Algebra,68: 94–112, 2020. https://doi.org/10.1080/03081087.2016.1256945 Our third published work corresponds with the third problem we have addressed. In this work the structure is the toughtest, with a potential value considered on every vertex, thus the operator is a positive semi– definite Schrödinger type operator and a partial electrical subdivision (only in some edges) is applied. Of course, the generalized resistance distance is the one that fits in this environment. 4. Á. Carmona, M. Mitjana and E. Monsó. Group inverse matrix of the normalized Laplacian on subdivision networks. Applicable analysis and discrete mathematics,14: 272–286, 2020. doi = 10.2298/AADM180420023C Finally, our fourth published work is devoted to the functional expression of the results of our second problem, where a simple electrically compatible subdivision of a network and the normalized Laplacian operator are considered. To end this chapter, this thesis memory is organized as follows. Chapter 3 gives an overview of Discrete Potential Theory, the mathematical framework we have worked in. Even though inspired in the works of Choquet and Deny about two centuries ago for the continuous field, our references here are from the colleagues of the MAPTHE research group, to which we proudly belong, [7, 8, 11, 12]. A brief introduction to the discrete counterpart of elliptic operators is presented: Laplacian and Schrödinger type. We justify the names. Moreover we prove the existence of their generalized inverse operators, called Green’s operator in every case. Also their associated kernels are presented. Chapter 4 is the core of our work. There the different cases that have produced our four now published works are treated. Case by case, the electrically compatible subdivision procedure is defined and the corresponding Poisson problem on the subdivided network is solved. This is done by taking advantage of a particular solution of a related Poisson problem posed on a given initial network, to which the subdivision operation is applied. The different cases of the three well known difference operators, combinatorial Laplacian, normalized Laplacian and Schrödinger type operators, are considered and the correspondent Green’s functions are obtained. We give a matrix interpretation of our results, as Green kernels can be identified with Moore–Penrose inverse matrices (or group inverse matrices) of the respective symmetric matrices associated with the mentioned operators. In Chapter 5 the definitions of the resistance distance and the Kirchhoff index are provided. The ideas behind the definitions are explained and their computation is adressed. In the case of networks, they are a quite straightforward generalization of the respective concepts well established on graphs in the seminal paper [58]. But in the case of the Schrödinger operator, the richness of the structure demands a brand new definition provided in [12]. Then, the computation of resistance distances and Kirchhoff indices for subdivision networks are obtained in the three reiteratively referred cases. The three last chapters contained in this memory are devoted to the presentation of the application of our results to some simple scenarios, to establish the future work in which we are determined to devote our efforts, and to explain some conclusions that we have obtained from our work during this time, respectively. Thus, in Chapter 6 simple networks as Star networks and Wheel networks are taken into account, and examples of the obtained results are provided so as the reader can get a better idea of the work we have done. Then, in Chapter 7, some more works that we are to be submited soon, open problems and further works that are still in mind are described at the last chapter. To end with, in Chapter 8 we have listed some interesting ideas, remarks and conclusions that we have obtained from the work done. The Bibliography used in our research is listed in the very last pages of this work, too. 3 Discrete Potential Theory Mathematical community has been for a long time interested in finding out explicit expressions for solutions of partial differential equations. Many efforts have been devoted to their resolution from a long time ago, many hurdles encountered have been fortunately overcame, but many others remain unfortunately unsolved. Computing solutions of such partial differential equations is a challenging task, even in numerical mathematics, mainly because of the physical domain where they are established. As many situations of real interest are treated, modelled and solved, considering elliptic partial differential equations in the continuous field, elliptic problems play a central role in mathematical physics. Two very well known examples are the Poisson equation ∆u=fon D where D ⊂ Rsis a given domain and f∈ C(D)is a given data function, and also the eigenvalue problem or Schrödinger’s equation −∆u=λu on D, with λ∈R.In both cases ∆denotes the classical Laplace operator given by ∆u=∂2u ∂x12+∂2u ∂x22+···+∂2u ∂xs2. The principal aim of the work we have developed is to contribute to the understanding of discrete elliptic problems on finite networks, where a particular operation that has a circuit theory inspiration has been applied. For this purpose, we have taken advantage of the so called discrete potential theory techniques. Thus, even though our work is centered in the discrete field, we use notations that are inspired in the continuous setting for elliptic operators because 22 Chapter 3. Discrete Potential Theory there is a strong symbiosis between both frameworks, see [47, 55] as an example. Indeed, sometimes solving a problem in the discrete setting can lead to the solution of its continuum version by a limit process. On the contrary, sometimes the relation between these two worlds does not work so easily. In this chapter, our goal is to introduce the terminology and results on discrete vector calculus on finite networks that we have used in this work. We define what a network is, the functional notation we use, and the geometric concepts (up to tangent space and vector fields) to justify basic difference operators that mimic the usual differential operators in the continuous case, in particular gradient and divergence. Thus, we explain that these discrete operators satisfy analogue properties to those fulfilled by self–adjoint second order elliptic continuous operators. In particular, they have associated quadratic forms and resolvent or Green kernel, too. The results we are about to show have been obtained by some members of our research group in [6, 7, 8, 9, 11, 23]. Particularly, the concept of tangent space is an identifying characteristic of our group. Other authors have also treated some of the topics presented in this chapter, see for instance [16, 19, 34, 36, 59]. 3.1 Preliminaries In this manuscript, we prefer to use a functional notation that emphasizes similarities between the situation of discrete structures (graphs and networks) and the continuous case (manifolds). We will consider real–valued functions defined on the vertex set of the graph, that can be identified so handled as real finite dimensional vectors, and real–valued functions defined on the edges set of the discrete structure as well. Moreover, we will also use the word Laplacian, as our principal discrete operator can be viewed as a proper discretization of the usual Laplace–Beltrami differential operator. Finally, operators between functional spaces will have their corresponding, kernels and inverses. Finally, a matrix version is also at disposal after giving a labelling on the network vertex set. 3.1.1 Graphs and networks Agraph Γ=(V, E)consists of a finite nonempty set V={x, y, z, . . .}of vertices (or nodes), and a second set Eof edges (or links) that are conceived as relationships between vertices. Thus E⊆V×Vso that {x, y} ∈ Eif and only if vertices xand yare to be considered as linked in some sense. Therefore, (y, x)∈Etoo. The number of vertices, |V|,is known as the order of the graph while the number of edges, |E|,is referred as the size of Γ. 3.1. Preliminaries 23 Given x, y ∈Vtwo different vertices in a graph, they are told to be adjacent (or neighbours) if and only if there exists an edge relating them. In this case, we write x∼yand the edge {x, y} ∈ Eis said to be incident on both xand y. The set of adjacent vertices to a given vertex xis N(x) = {y∈V:y∼x} and the degree of a vertex is defined as the cardinality of N(x),that is deg(x) = |N(x)|.When a couple of vertices in V, say xand y, be connected by a sequence of `+ 1 different vertices {x=x1, x2,··· , x`, x`+1 =y} ⊆ V such that xi∼xi+1 for all i= 1, . . . , `, then we say that there is a path between xand yand we write Pxy when referring to the set of all `+ 1 vertices together with the `edges {xi, xi+1}for all i= 1, . . . , `. We also say that `(Pxy) = `is the length of this path Pxy. Graphs can be sketched in two dimensional representations by drawing points for vertices, and segments for the edges that join corresponding neighbours. See [20, 29] for basic concept on graph theory. In graph theory, vertices are all considered identical in nature, whatever they represent, as if they behave all exactly in the same way, with no established differences among them. Hence, no different roles can be assumed, except by the number of their connections to other vertices, as they may have different degree. Similarly, edges are considered solely as connections. They are entities that just establish (or not) a relationship between vertices. There is no possibility of discrimination among them, as if all links were equal, and the sole question that can be treated is whether they exist or not. When a positive value is assigned to every edge of a given graph Γintroducing the possibility of differentiating between connections, allowing the possibility of modelling links between vertices differently, the discrete structure is called network. Thus, a network Γ=(V, E, c)is a graph (V, E)endowed with a nonnegative function c:V×V→[0,+∞),such that c(x, y)>0for every pair x, y when {x, y} ∈ Eand, therefore, c(x, y)=0when {x, y}/∈E. We call this function conductance, and consider the value c(x, y)as a weight assigned to the corresponding edge {x, y}whenever it exists. Moreover, this conductance function is symmetric as c(x, y) = c(y, x)because {x, y}and {y, x}are considered as the same edge. Then, the generalized degree of a vertex x∈Vis κ(x) = X y∼x c(x, y),and the reciprocal function rdefined as r(x, y)=1/c(x, y)for x∼y, is called resistance function. As the particular case of c(x, y)being one on every edge where is non–null puts us back in the case of a simple graph, where no differences between edges can be considered, we will also use Γto denote a graph. In this work we will only consider simple networks; that is, with no loops, i.e. no edges that link a vertex with itself will be considered, nor multiples edges, so there will exist at most one connection between every possible pair 30 Chapter 3. Discrete Potential Theory And finally the corresponding version of Gauss theorem is X x∈VL(u)(x) = 0. Easily from the previous results, we also obtain that the Laplacian of Γis self–adjoint and positive semi–definite. Moreover L(u) = 0 if and only if uis constant. Hence, when restricted to its kernel, the Laplacian operator is an automorphism. 3.4.2 Schrödinger type operators Given a function q∈ C(V),we define a Schrödinger operator on Γas the linear operator Lq:C(V)→ C(V)that assigns to every u∈ C(V)the function Lq(u)(x) = L(u)(x) + q(x)u(x). While we refer to qas the potential, some authors use the term ground–state as it might be interpreted as a connection of each vertex in a network with a conductor medium with null potential. Instead of considering a Schrödinger operator as a perturbation of the combinatorial Laplacian, which it is, we prefer to look at it as an assignation of a real number (positive, negative or zero) to every single vertex in the structure, allowing the possibility of differentiating between vertices somehow (and not only because of having different degree). Hence, by introducing Schrödinger operators we get to satisfy our wish of working with discrete structures that consider the possibility of distinguishing both constitutive elements of a network; vertices by qand also edges by c. Clearly Lqis also a self–adjoint operator and defines a bilinear form Eq(u, v) = hu, Lq(v)ithat is called the energy of Lq.Applying the first Green identity for the Laplacian it turns out that Eq(u, v) = 1 2X x,y∈V c(x, y)u(x)−u(y)v(x)−v(y)+X x∈V q(x)u(x)v(x) so if q≥0then the energy of Lqis positive semi–definite. What we will call a weight is a function ω∈ C(V),such that ω > 0on V and also hω, ωi= 1.We will denote as Ω(V)the set of positive and unitary, weight functions. For every weight ω, we define qωthe potential associated with ω, as qω(x) = −1 ω(x)L(ω)(x), x ∈V. 3.4. Second order difference operators 31 Therefore, it is qω(x) = −κ(x) + 1 ω(x)X y∈V c(x, y)ω(y)for every x∈V. So a weight and its associated potential are orthogonal functions and therefore qωmust take positive and negative values except when the weight is constant, in which case its associated potential vanishes at every vertex and its corresponding Schrödinger operator Lqω=L0=Lis the Laplacian. Potentials associated with a weight do determine, up to a multiplicative positive constant, the weight function. That is, if ω1and ω2are weight functions, it is qω1=qω2if and only if ω1=aω2for some a > 0.On the other hand when qω16=qω2, qω1determines a family of functions qfor which Lqis positive semi–definite and is essentially different from the family determined by qω2.More properties of these potential associated with weight functions can be found in [7]. By using the well known Perron–Frobenius theorem every potential function qis related to a potential function associated with a weight qωin the following terms: given q∈ C(V),there exists a unique ω∈Ω(V)and λ∈Rsuch that q=qω+λ (see [7] again for a detailed justification of this very important result). So there is another characterization of Schrödinger operators, Lq(u)(x) = L(u)(x) + q(x)u(x) = Lqωu(x) + λu(x). An expression for Lqωis obtained by applying the so called Doob’s Transform once a weight is given. Hence, for every u∈ C(V)it is L(u)(x) + qω(x)u(x) = 1 ω(x)X y∈V c(x, y)ω(x)ω(y)u(x) ω(x)−u(y) ω(y), x ∈V. In addition, for every u, v ∈ C(V)we obtain that Eqω(u, v)+ X x∈V qω(x)u(x)v(x) = 1 2X x,y∈V c(x, y)ω(x)ω(y)u(x) ω(x)−u(y) ω(y)v(x) ω(x)−v(y) ω(y). So now we are ready to set a necessary and sufficient condition for the positive semi–definiteness of Schrödinger operators, which is a result that evidently has a continuous counterpart known as the Energy principle. Once q= qω+λ, then Lqis positive semi–definite if and only if λ≥0,and positive definite if and only if λ > 0.Moreover, when λ= 0,Lq(u)=0if and only if u=aω for some a∈R. 32 Chapter 3. Discrete Potential Theory Also, as min hu,ui=1 {Eq(u)} ≥ λ, it is Eq(u) = λif and only if u=±ω. Hence Lq(ω) = λω and λturns to be the lowest eigenvalue of Lq,and it is simple. In the positive semi–definite case, when λ= 0 and q=qω,it is Lqω⊥ωand therefore if u∈ C(V)is such that Lqω(u)≥0,then Lqω(u)=0and u=aω with a∈R. 3.4.3 The normalized Laplacian The concept of Schrödinger operator encompasses other widely used discrete operators as, for example, the so called normalized Laplacian introduced in [35] and defined as Lu(x) = 1 κ(x)X y∈V c(x, y) u(x) pκ(x)−u(y) pκ(y)! for a connected network with conductance function c. If the size of the subjacent graph is m, then the normalized Laplacian on (V, E, c)coincides with the non–singular positive semi–definite Schrödinger operator on (V, E, ˆc)where the conductance function is ˆc(x, y) = c(x, y) pκ(x)pκ(y),considering ω=1 2m√κ and obviously λ= 0,thus L=Lqω,applied on the same graph but considered as two different networks. 3.5 Green’s function for Poisson and Dirichlet problems In this work we have considered solving Poisson and Dirichlet boundary value problems on networks associated with linear operators as the combinatorial Laplacian, the normalized Laplacian and Schrödinger type operators as well. In this section we introduce the required concepts to solve these problems. The so called Green’s function turn to be critical in the sense it can be considered as the universal solver. 3.5.1 Poisson and Dirichlet boundary value problems on networks Roughly speaking, a Poisson problem on Γis when the domain where the condition has to be validated is the hole vertex set V, whereas a Dirichlet problem establishes a condition only in a proper subset F⊂Vwhile adding the values of the solution on the boundary ∂F. 3.5. Green’s function for Poisson and Dirichlet problems 33 More explicitly, let Ldenote now whatever of our three second order difference linear operators, the combinatorial Laplacian or the normalized Laplacian or more generalized Schrödinger type operator. Then, given f∈ C(V) aPoisson problem with data fis set so as we want to find out which is u∈ C(V)such that L(u) = f on the whole V. On the other hand, a Dirichlet boundary value problem is posed once a proper subset F⊂Vand two data functions f∈ C(V)and g∈ C(F)are given. Therefore, we are interested in finding u∈ C(V)such that L(u) = fon F u=gon ∂F. It is worth to mention that both Poisson and Dirichlet boundary value problems are related not only to a domain (in our case the vertex set associated with the network Γ, or a subset of it), but also to a particular linear operator to be considered and solved. 3.5.2 Green operators and Green’s kernel functions Now we assume that both, combinatorial Laplacian and Schrödinger type operators2, are positive semi–definite. We have seen that it is always the case for the first one, and that we have to consider q=qω+λ, for some ω∈ Ω(V)and λ≥0,for the second one. Provided this situation, we construct kernels associated with their respective inverse operators that correspond to Poisson problems. Analogously to the well known continuous case, such inverse operators will be called Green operators. We start recalling fundamental notions about operators and their associated kernels that we have exposed in section 3.2.2 and assuming F1=F2=V. We will remark the conditions that assure existence and uniqueness of the inverse operators, list a few properties that are satisfied by them and finally build the associated kernel that is known as Green’s kernel function or Green’s function for short. Generally speaking, if K:V×V→Ris a kernel in Vthen its associated endomorphism K:C(V)→ C(V)is defined as (K(u))(x) = X y∈V K(x, y)u(y),for every x∈V. Conversely, any endomorphism in C(V)determines a kernel in Vby K(x, y) = K(εy)(x)for every pair x, y ∈V. 2We consider the normalized Laplacian as a "particular" case 34 Chapter 3. Discrete Potential Theory In this context, an operator Kis self–adjoint (that is hK(u), vi=hu, K(v)i for every u, v ∈ C(V)) if and only if its related kernel Kis a symmetric function (K(x, y) = K(y, x)for all x, y ∈V). 3.5.3 Inverse operator for the Laplacian operator Let us now denote 1∈ C(V)the constant function 1(x)=1,for every x∈V. It turns out that ||1||2=|V|.Given f∈ C(V),the Poisson problem on Γfor the Laplace operator consists in finding u∈ C(V)such that L(u)(x) = f(x),for every x∈V. As we have previously seen, the kernel of the Laplacian operator is the set of constant functions, so we can consider the orthogonal projection onto kerL=span{1},P:C(V)→ker(L)defined as P(f) = hf, 1i h1,1i·1,for every f∈ C(V)so that (P(f)) (x) = Py∈Vf(y)1(y) |V|·1(x) = 1 |V|Py∈Vf(y)is the constant function with value equal to the sum of all values that fattains. It is clear, see below in Figure 3.1 for a representation of the Laplacian operator, that L◦P = 0.As Gauss theorem holds for the Laplacian operator, L(u)∈(kerL)⊥or equivalently P ◦L = 0,as well. Consequently we have a characterization for data function on Poisson problems for the corresponding problem being compatible and therefore solutions exist. Therefore, the set of all solutions to a Poisson problem L(u) = f−P(f)is a one–parameter family {u+µ1, µ ∈R},with uthe unique function that exists by the previous results. Again Figure 3.1 illustrates this fact, as there is exactly one point (for a function) in every line parallel to 1(for a one– parameter family) that is in 1⊥. Thus it is possible to fix a particular solution in some sense because an orthogonal to 1solution of a compatible Poisson problem can be always found. So there is a Fredholm’s alternative discrete version that also applies in this discrete setting, see [8]. Given f∈ C(V),the Poisson problem L(u) = fis consistent if and only if P(f)=0.Then, there exists a unique solution such that P(u) = 0. Therefore and so to speak, in some sense, there is existence and uniqueness of solutions for a Poisson problem given the Laplacian operator. Now we consider the operator that assigns to every function f∈ C(V)the unique u∈ C(V)such that L(u) = (I −P)(f)and hu, 1i= 0. 3.5. Green’s function for Poisson and Dirichlet problems 35 u 1⊥ L G 1⊥ 0 0 1 (I − P)(u) 1=kerL C(V) C(V) P(u) u 1⊥ 1⊥ 0 0 1=kerG f P(f) 1 C(V) C(V) (I − P)(f) Figure 3.1 Two pictures about the Laplacian and Green operators in relation with a Poisson problem L(u) = f We will call it the Green operator and will denote it by Gso as G:C(V)→ C(V),such that G(f) = u. See again Figure 3.1, now above, for a geometric interpretation. As the network is connected and as happens with the Laplacian operator, the Green operator, when restricted to the space 1⊥,is also an automorphism. Then it is clear that G◦P = 0.By definition G(f)∈1⊥so P◦G = 0 as well. Moreover, this Green operator satisfies nice properties such that for instance being self–adjoint and positive semi–definite. Also the Green operator of f∈ C(V)is orthogonal to fonly when fis constant, or hG(f), fi= 0 if and only if f=a1for a∈R. Therefore, the associated kernel G:V×V→Rdefined for every pair x, y ∈ Vas G(x, y) = G(εy)(x)is called Green’s kernel function. We note that it is symmetric, as Gis self–adjoint, and that u(x) = X y∈V G(x, y)f(y)is the unique solution orthogonal to 1of the Poisson problem L(u) = (I −P)(f) for every f∈ C(V). Hence, the well known relation between an operator and its associated kernel enables us, again, to characterize the Green kernel of Γby considering a family of solutions of suitable consistent Poisson problems. Let us define for every y∈V, the function Gy∈ C(V)defined by Gy(x) = G(x, y), x ∈V. It can be characterized by L(Gy) = εy−1 |V|1,hGy,1i= 0. 36 Chapter 3. Discrete Potential Theory So, from the relationship between Land G,it turns out that L◦G=G◦L = I − P.Thus, when restricted to 1⊥,it is L◦G=G ◦ L =Iobviously. Therefore, it is L◦G◦L=L◦(I −P) = L,and G ◦L◦G =G ◦(I −P) = G by applying that L◦P =P ◦L =G ◦P =P ◦G = 0.So both operators are generalized inverse operators one of each other and our goal is accomplished. 3.5.4 Inverse operator for a Schrödinger type operator Once we have presented the so called Green operator and its respective Green’s kernel for L,the Laplacian operator on a network Γ,we face now the study of their counterparts in the case of a Schrödinger operator Lqby reproducing previous arguments and definitions. Now a Poisson problem consists in, given f∈ C(V),figuring out u∈ C(V), satisfying Lq(u) = f, for all x∈V. We are concerned with Schrödinger type operators that have good properties, so we consider that the potential q∈ C(V)is q=qω+λfor some ω∈Ω(V) and λ≥0.Two cases have to be treated separately: when λ > 0the self– adjoint operator is positive definite, so invertible; while when λ= 0 it is self–adjoint and positive semi–definite, with a null simple eigenvalue as the network is connected. As we shall see, in both cases the Green operator is well defined, self–adjoint, and denoted by Gqwith no ambiguity because of the scenario. Moreover, the associated kernel Gq:V×V→R,that is constructed by analogous procedures so as Gq(x, y) = Gq(εy)(x),for any x, y ∈V, is called the Green function and it turns out to be symmetric. We notably remark, in a unifying notation, that Gq(ω) = λ†ω, where λ†= λ−1in the invertible case λ > 0,while λ†= 0 in the singular case, that is λ= 0. Case (i): λ > 0,Lqpositive definite When λ > 0the Schrödinger operator Lqis an isomorphism on C(V),as there is no kernel to consider, ( i.e. ker(Lq) = 0). Then, a Poisson problem Lq(u) = f, for all x∈V, is always, for every data function f∈ C(V), consistent. Therefore, we can define its inverse operator Gq:C(V)→ C(V), such that Gq(f) = u, for every f∈ C(V).This inverse operator will be called Green operator of Γ. 3.5. Green’s function for Poisson and Dirichlet problems 37 Obviously it is Lq◦Gq=Gq◦Lq=I.The Green operator is positive definite in this case by applying the positive semi–definiteness of Eq.Moreover it is also a self–adjoint operator in the sense that X x∈V g(x)Gq(f)(x) = X x∈V f(x)Gq(g)(x),for all f, g ∈ C(V). The Green kernel of Γis the kernel associated with the previous Green operator, is denoted by Gq=Gq(x, y)and is symmetric again. Then, the sole solution to the Poisson problem Lq(u) = fon V, can be recovered from the data function f∈ C(V)by u(x) = X y∈V Gq(x, y)f(y),for all x∈V. Finally, the relation between operators and their associated kernels enables us to characterize the Green kernel as the set of solutions of a suitable battery of Poisson problems. As Lqis an isomorphism, we consider for every y∈V, the function (Gq)y(x) = Gq(εy)(x)for every xon V, and finally we define Gq(x, y) = (Gq)y(x)so this component function is symmetric and characterized by Lq(Gy) = εyon V. Case (ii): λ= 0,Lqpositive semi–definite When λ= 0, the Schrödinger operator is a singular, self–adjoint and positive semi–definite operator, as the Laplacian operator is. We will denote again as Lqeven though, as λvanishes, it should be a Lqωin fact, for some ω∈Ω(V). Let us consider the vector space ker(Lq)which is now the linear space generated by ω. Therefore, the orthogonal projection onto ker(Lq) = span{ω},is P:C(V)→ hωidefined as P(f) = hf, ωi·ω, for every f∈ C(V).It is clear that Lq◦P = 0,and also that P ◦Lq= 0. Consequently, we have a characterization for data function on Poisson problems so there exist a solution. Moreover, as in the Laplacian case, a Fredholm’s alternative holds: consistency is assured if and only if data functions are orthogonal to the weight function, and there is a unique orthogonal to the weight function solution of the problem (when there is) or mathematical spoken given ω∈Ω(V)and f∈ C(V),then the corresponding Poisson problem for the Schrödinger operator Lq(u) = fis consistent if and only if P(f)=0.Moreover, there exists a unique solution such that P(u)=0. Hence, for each f∈ C(V),as f−P(f)is in (ker(Lq))⊥,there exists u∈ C(V) such that Lq(u) = f− P(f).Then, the set of all solutions of the Poisson problem is v∈ C(V) : v=u+aω for some a∈R.And there is just one function in this set that is orthogonal to ω. 38 Chapter 3. Discrete Potential Theory Now is clear how to define the desired inverse operator. Let us consider the operator that assigns to every function f∈ C(V)the unique u∈ C(V)such that Lq(u)=(I −P)(f)and hu, ωi= 0. Of course, we will call it the Green operator and we will denote it by Gqso as Gq:C(V)→ C(V),such that Gq(f) = u. As the network is connected, the Green operator, when restricted to the space ω⊥,is an automorphism. So Gq◦P = 0 and P ◦Gq= 0 as well. Moreover, this Green operator also satisfies the nice properties of being self– adjoint and positive semi–definite. And it sends hωito hωi⊥,or more precisely hGq(f), fi= 0 if and only if f=aω for a∈R. With all that, its corresponding kernel Gq:V×V→Rdefined as Gq(x, y) = Gq(εy)(x)for every pair x, y ∈Vis called Green’s kernel function. We note that it is symmetric, as Gqis self–adjoint, and hence u(x) = X y∈V Gq(x, y)f(y) is the unique solution orthogonal to ωof the Poisson problem Lq(u) = (I −P)(f)for every f∈ C(V),now in the case that q=qωfor some weight function ω∈Ω(V). As in the previous cases, the relation between an operator and its associated kernel enables us, again, to characterize the Green kernel of Γas solutions of a battery of appropriate consistent Poisson problems. Let us define for every y∈V, then function (Gq)y∈ C(V)defined by (Gq)y(x) = Gq(x, y), x ∈Vis characterized by L((Gq)y)=(I −P)εy=εy−ω(y)ω, h(Gq)y, ωi= 0. Finally, to end this section and this chapter too, from the relationship between the singular Schrödinger operator Lqand its inverse operator Gq,it turns out that Lq◦Gq=Gq◦Lq=I−P.Analogously to the Laplacian case, it is Lq◦Gq=Gq◦Lq=Iwhen restricted to ω⊥.Therefore, it is true that Lq◦Gq◦Lq=Lq◦(I −P) = Lq,and Gq◦Lq◦Gq=Gq◦(I −P) = Gq and we can state that both operators are generalized inverse operators one of each other. 3.6 Matrix interpretation As we are concerned with finite discrete structures, both size and order of the subjacent graph are finite. Thus it is quite straightforward to obtain a 3.6. Matrix interpretation 39 vectorial version of what functions are and also a matrix interpretation for linear operators and their correspondent kernels. Hence, given a labelling of a connected network Γ, that is supposing that V={x1, ..., xn},the conductance c(xi, xj)≥0,for every i, j = 1, . . . , n then each u∈ C(V)can be identified with a vector of ncomponents (now |V|=n).Hence u= [u(x1), . . . , u(xn)]T∈Rn. Therefore, the combinatorial Laplacian of Γis identified with the singular irreducible M–matrix L=            κ(x1)−c(x1, x2)··· −c(x1, xn) −c(x2, x1)κ(x2)··· −c(x2, xn) . . .. . ..... . . −c(xn, x1)−c(xn, x2)··· κ(xn)            . Clearly, this matrix is symmetric and diagonally dominant and hence it is positive semi–definite. Moreover, it is singular and 0is a simple eigenvalue whose associated eigenvectors are constant. In the particular case of a graph, that is when c(x, y)=1when non–null, the Laplacian matrix is a very powerful tool that is used to analyze structures from the connectivity point of view (counting connected parts, algebraic connectivity, expanding properties, isoperimetric number and many more). Similarly, we can also have in mind that its inverse operator, what is called the Green operator, has its own matrix counterpart, say Gcorresponding to the Green’s kernel function of course, which is symmetric. Therefore, so it is G. Moreover, the very well known Moore–Penrose conditions for a generalized inverse hold, as in this case it is LGL =L GLG =G (LG)T=LG (GL)T=GL. Hence Gis the Moore–Penrose generalized inverse of the Laplacian matrix L, denoted as G=L†.See [17] for a general introduction to generalized inverses. It is possibly to translate the former discussion to the case of a Schrödinger type operator. 46 Chapter 4. Subdivision networks Proposition 4.1.3. Let ΓSbe the subdivision network of Γ, then for any x, z ∈Vand vxy, vzt ∈V0, the Green kernel of ΓSis given by GS(x, z) = G(x, z)−1 n+mX `∈VhG(x, `) + G(z, `)iπS(`) + β, GS(vxy, z) = α(x, y)G(x, z) + α(y, x)G(y, z) −1 n+mX `∈Vhα(x, y)G(x, `) + α(y, x)G(y, `) + G(z, `)iπS(`) −1 (n+m)k(vxy)+β, GS(vxy, vzt) = α(z, t)α(x, y)G(x, z) + α(y, x)G(y, z) +α(t, z)α(x, y)G(x, t) + α(y, x)G(y, t) −1 n+mX `∈Vhα(x, y)G(x, `) + α(y, x)G(y, `)iπS(`) −1 n+mX `∈Vhα(z, t)G(z, `) + α(t, z)G(t, `)iπS(`) +εvzt (vxy) k(vxy)−1 (n+m)k(vxy)−1 (n+m)k(vzt)+β. Proof. Suppose z∈V, and let hz=εz−1 n+m.Then, for every x∈V hz(x) = εz(x)−1 n+m−1 n+mX y∼x α(x, y) = εz(x)−1 n+m(1 + πS(x)). Hence, we now need to solve the Poisson problem L(uz) = hz.Using the Green kernel for Γ,we obtain uz(x) = G(εz)(x)−1 n+mX `∈V G(x, `)πS(`) = G(x, z)−1 n+mX `∈V G(x, `)πS(`). Then, from Corollary 4.3.2 GS z(x) = uhz z(x)−1 (n+m)X r∼s hz(vrs) k(vrs) −1 (n+m)X r∼s [α(r, s)uz(r) + α(s, r)uz(s)] 4.1. Subdivision networks for combinatorial Laplacian 47 and GS z(x) = G(x, z)−1 n+mX `∈V G(x, `)πS(`) + 1 (n+m)2X r∼s 1 k(vrs) −1 (n+m)X r∼s α(r, s)"G(r, z)−1 n+mX `∈V G(r, `)πS(`)# −1 (n+m)X r∼s α(s, r)"G(s, z)−1 n+mX `∈V G(s, `)πS(`)# =G(x, z)−1 n+mX `∈VhG(x, `) + G(z, `)iπS(`) +1 (n+m)2X r,s G(s, r)πS(r)πS(s) + 1 (n+m)2X r∼s 1 k(vrs). Now if z∈V, then for every vxy ∈V0 GS z(vxy) = hz(vxy) k(vxy)+α(x, y)uz(x) + α(y, x)uz(y) −1 (n+m)X r∼s hz(vrs) k(vrs)−1 (n+m)X r∼s [α(r, s)uz(r) + α(s, r)uz(s)] GS z(vxy) = −1 (n+m)k(vxy)+α(x, y)G(x, z) + α(y, x)G(y, z) −1 n+mX `∈Vα(x, y)G(x, `) + α(y, x)G(y, `)πS(`) +1 (n+m)2X r∼s 1 k(vrs) −1 (n+m)X r∼s α(r, s)"G(r, z)−1 n+mX `∈V G(r, `)πS(`)# −1 (n+m)X r∼s α(s, r)"G(s, z)−1 n+mX `∈V G(s, `)πS(`)# GS z(vxy) = −1 (n+m)k(vxy)+α(x, y)G(x, z) + α(y, x)G(y, z) −1 n+mX `∈Vα(x, y)G(x, `) + α(y, x)G(y, `)πS(`) +1 (n+m)2X r∼s 1 k(vrs)−1 n+mX `∈VhG(z, `)iπS(`) +1 (n+m)2X r,s G(s, r)πS(r)πS(s) 48 Chapter 4. Subdivision networks So finally, GS z(vxy) = −1 (n+m)k(vxy)+α(x, y)G(x, z) + α(y, x)G(y, z) −1 n+mX `∈Vα(x, y)G(x, `) + α(y, x)G(y, `) + G(z, `)πS(`) +1 (n+m)2X r∼s 1 k(vrs)+1 (n+m)2X r,s G(s, r)πS(r)πS(s). Suppose now we fix vzt ∈V. The compatible data function to take into account is hvzt =εvzt −1 n+m.Then, for every x∈Vthe contraction to be used in the basis network Γis hvzt (x) = εvzt (x)−1 n+m+X y∈V α(x, y)εvzt (vxy)−1 n+m =−1 n+m(1 + πS(x)) + α(z, t)εz(x) + α(t, z)εt(x). Hence, the Poisson problem to solve is L(uvzt ) = hvzt ,and, using Green’s kernel for Γ,we obtain that the solution to be extended is uvzt (x) = −1 n+mX `∈V G(x, `)πS(`) + α(z, t)G(x, z) + α(t, z)G(x, t). Then, by applying again Corollary 4.3.2 Green’s function on ΓSon the new generated vertices is GS vzt (vxy) = hvzt (vxy) k(vxy)+α(x, y)uvzt (x) + α(y, x)uvzt (y) −1 (n+m)X r∼s hvzt (vrs) k(vrs) −1 (n+m)X r∼s [α(r, s)uvzt (r) + α(s, r)uvzt (s)] 4.1. Subdivision networks for combinatorial Laplacian 49 Now substituting we get that GS vzt (vxy) = εvzt (vxy) k(vxy)−1 (n+m)k(vxy) −1 n+mX `∈Vα(x, y)G(x, `) + α(y, x)G(y, `)πS(`) +α(z, t)α(x, y)G(x, z) + α(y, x)G(y, z) +α(t, z)α(x, y)G(x, t) + α(y, x)G(y, t) −1 (n+m)k(vzt)+1 (n+m)2X r∼s 1 k(vrs) −1 n+mX `∈Vα(z, t)G(z, `) + α(t, z)G(t, `)πS(`) +1 (n+m)2X r,s∈V G(r, s)πS(r)πS(s). And finally, GS vzt (vxy) = α(z, t)α(x, y)G(x, z) + α(y, x)G(y, z) +α(t, z)α(x, y)G(x, t) + α(y, x)G(y, t) −1 n+mX `∈Vα(x, y)G(x, `) + α(y, x)G(y, `)πS(`) −1 n+mX `∈Vα(z, t)G(z, `) + α(t, z)G(t, `)πS(`) +εvzt (vxy) k(vxy)−1 (n+m)k(vxy)−1 (n+m)k(vzt) +1 (n+m)2X r∼s 1 k(vrs)+1 (n+m)2X r,s∈V G(r, s)πS(r)πS(s). In particular, if Γis a k–regular graph and we consider the standard subdivision graph; that is c(x, vxy) = c(y, vxy)=2,we get the following result. Corollary 4.1.4. Let ΓSbe the standard subdivision graph of a k–regular graph, Γ; then for any x, z ∈Vand vxy, vzt ∈V0, the Green kernel of ΓSis 50 Chapter 4. Subdivision networks given by GS(x, z) = G(x, z) + k 2n(2 + k)2, GS(vxy, z) = 1 2G(x, z) + G(y, z)−1 n(2 + k)2, GS(vxy, vzt) = 1 4G(x, z) + G(y, z) + G(x, t) + G(y, t) +εvzt (vxy)−(4 + k) 2n(2 + k)2. 4.2 Subdivision networks for the normalized Laplacian Our second step in exploring the possibilities for the electrical subdivision procedure was set in the context of random walks and Markov chains, as we studied also the compatibility of related Poisson problems on a given network and its subdivision counterpart for the well known normalized Laplacian operator. So, the idea of the modification of a given network was not at stake at that moment, but the idea of the Poisson problem was no more a typical diffusion setting. The conclusion of our study was at first glance a little bit disappointing as the result we obtained forces a very restrictive idea of electrical subdivision for this operator. However, due to the particular use of the degree concept in the definition of the normalized Laplacian operator, with plenty of square roots of sums, subdivision of edges must follow a very particular pattern because of technicalities. Hence the exciting network operation of subdivision has a rather short run when used in such a random walks scenario. But this, at the end, is in perfect concordance with the mismatching of the concepts of random walks and electrical circuits or flows, and subdivision procedure as successful as it were in the previous case of a diffusion problem. Or, explained in other words, the relation of conductances (or resistances, we don’t care) in electrical circuits with ˆc(x, y) = c(x, y) pκ(x)pκ(y),when considering ω=1 2m√κ and obviously λ= 0 is, let’s say, at least rather intrincated. Thus a subdivision network ΓS= (VS, ES, cS)of Γis now obtained in a very similar way than the previous scenario, by inserting a new vertex in every edge, so that each {x, y} ∈ Eis replaced by two new edges, say {x, vxy} and {vxy, y}where vxy is the new inserted vertex, see [75] where a classical subdivision process is considered. The important point now is that we have had to define conductances on the new edges as cS(x, vxy) = cS(y, vxy) = 4.2. Subdivision networks for the normalized Laplacian 51 2c(x, y),so that, electrical compatibility is still fulfilled, but in a somewhat graph but not network manner. So it is still 1 c(x, y)=1 cS(x, vxy)+1 cS(y, vxy) but more in detail it turns 1 c(x, y)=1 2c(x, y)+1 2c(y, x)and there is just one possibility to accomplish the network structural operation. Of course then the degree function on ΓS,kS∈ C(VS),satisfies kS(x)=2k(x)for any x∈V, and kS(vxy) = 4c(x, y)for those vertices in V0.Moreover, it holds that vol(ΓS) = 4vol(Γ). So we now present the precise relationship between a solution of a compatible Poisson problem for the normalized Laplacian on a subdivision network ΓSand a solution of a conveniently well posed Poisson problem for the normalized Laplacian on the base network Γ. 4.2.1 Related Poisson problems Mimicking the preceding subsection 4.1.1, we also recall what is the normalized Laplacian operator for a subdivision network, denoted now as LS,and defined for any u∈ C(VS)as LS(u)(x) = 1 pκS(x)X y∈V c(x, vxy) u(x) pκS(x)−u(vxy) pκS(vxy)!, x ∈V, LS(u)(vxy) = 1 pκS(vxy)(c(x, vxy) u(vxy) pκS(vxy)−u(x) pκS(x)! +c(y, vxy) u(vxy) pκS(vxy)−u(y) pκS(y))!), vxy ∈V0. As we proceed similarly to the previous case, we also put in place two functional operators, let’s say a contraction and an extension related to. Let h∈ C(VS)we define its contraction to C(V)as h(x) = h(x) + 1 p2k(x)X y∼xpc(x, y)h(vxy). Now unfortunately with no ideological context, just because it works. Honestly, we have never seen in the literature a significance for pc(x, y)and we have arrived to non satisfactory conclusions when trying to understand what could be a possible meaning for it. Also we briefly will consider, for a couple u∈ C(V)and h∈ C(VS)the extension of u(the former) related to h(the latter) to C(VS), such as uh(vxy) = h(vxy) + pc(x, y) √2 u(x) pk(x)+u(y) pk(y)! 52 Chapter 4. Subdivision networks for vxy ∈V0, while uh(x) = u(x)for those vertices in V. The following result links the solution of a given compatible Poisson problem in the subdivision network with an appropriate and also compatible Poisson problem on the base network. Theorem 4.2.1. Given h∈ C(VS)such that hh, √kSiVS= 0,then hh, √kiV= 0.Moreover, u∈ C(VS)is a solution of the Poisson equation LS(u) = hin VSiff u=u|Vis a solution of the Poisson equation L(u)=2hin V. In this case, the identity u=uhholds. Proof. Firstly we note that Dh, √kEV=1 √2Dh, √kSEVSas X x∈V h(x)pk(x) = X x∈V h(x)skS(x) 2 +1 √2X x∈V 1 pk(x)X y∼xpc(x, y)h(vxy)pk(x) =1 √2X x∈V h(x)qkS(x) + 1 √2X vxy∈V0 h(vxy)qkS(vxy). So the first statement holds. Then, LSu(vxy) = u(vxy)−cS(vxy, x) pkS(vxy)pkS(x)u(x)−cS(vxy, y) pkS(vxy)pkS(y)u(y) =u(vxy)−pc(x, y) √2 u(x) pk(x)−pc(x, y) √2 u(y) pk(y). So we obtain that, u(vxy) = LSu(vxy) + pc(x, y) √2 u(x) pk(x)+u(y) pk(y)!. Also, for the former vertex in the given network, LSu(x) = 1 pkS(x)X vxy∼x cS(x, vxy)"u(x) pkS(x)−u(vxy) pkS(vxy)#. 4.2. Subdivision networks for the normalized Laplacian 53 Substituting the precedent expression for u(vxy)we obtain LSu(x) = X y∼x c(x, y) 2pk(x)"2u(x) pk(x)−√2LSu(vxy) pc(x, y)−u(x) pk(x)−u(y) pk(y)# =1 2pk(x)X y∼x c(x, y) u(x) pk(x)−u(y) pk(y)! −1 p2k(x)X y∼xpc(x, y)LSu(vxy). Finally, we get, if u=u|V LS(u)(x) = 1 2L(u)(x)−1 p2k(x)X vxy∼xpc(x, y)LSu(vxy). So, for short, we have proven that given a Poisson problem with a compatible data function on ΓS,it can be contracted to a compatible data function on Γso as a solution of this related Poisson problem on Γexpands to a solution of the initial given Poisson problem on the subdivided network. Now, in order to choose a particular solution of the Poisson problem on the subdivided network, as in the previous section we can find the precise value for the constant because the following holds. Corollary 4.2.2. Given h∈ C(VS), such that hh, √kSiVS= 0,let h∈ C(V) be its contraction to V, let u∈ C(V)be the unique solution of L(u) = 2h that satisfies hu, √kiV= 0 and let be the constant λ=−1 2vol(Γ) X r∼s h(vrs)pc(r, s). Then, u⊥=uh+λ√kS∈ C(VS)is the unique solution of the Poisson problem LS(u) = hthat satisfies hu⊥,√kSiVS= 0.Specifically, u⊥(x) = u(x)−pk(x) √2vol(Γ) X r∼s h(vrs)pc(r, s), u⊥(vxy) = h(vxy) + pc(x, y) √2 u(x) pk(x)+u(y) pk(y)! −pc(x, y) vol(Γ) X r∼s h(vrs)pc(r, s), for any x∈Vand vxy ∈V0. 54 Chapter 4. Subdivision networks Proof. As two solutions differ on a multiple of √kS, we have that u⊥= uh+γ√kS,γ∈R. Then, 0 = hu⊥,√kSiVS=huh,√kSiVS+γX x∈VS kS(x) =√2X x∈V u(x)pk(x) + X vxy∈V0 uh(vxy)qkS(vxy) + γvol(ΓS) = 2 X vxy∈V0 uh(vxy)pc(x, y)+4γvol(Γ), because hu, √kiV= 0,and hence λ=−1 2vol(Γ) X r∼s uh(vrs)pc(r, s) =−1 2vol(Γ) X r∼s"h(vrs)pc(r, s) + c(r, s) √2 u(r) pk(r)+u(s) pk(s)!# =−1 2vol(Γ) X r∼s h(vrs)pc(r, s)−1 2√2vol(Γ) X r∈V u(r) pk(r)X s∼r c(r, s) =−1 2vol(Γ) X r∼s h(vrs)pc(r, s)−1 2√2vol(Γ) X r∈V u(r)pk(r) =−1 2vol(Γ) X r∼s h(vrs)pc(r, s). 4.2.2 Related Green’s functions Taking into account the relation between both Poisson problems for the normalized Laplacian on ΓSand on Γ, we obtain the expression of the Green function for the normalized Laplacian of the subdivision network GS,in terms of the Green function of the base network G. Theorem 4.2.3. Let ΓSbe the subdivision network of Γ, then for any x, z ∈ Vand vxy, vzt ∈V0, the Green function of ΓSis given by GS(x, z) = 2G(x, z) + pk(x)pk(z) 4vol(Γ) , GS(vxy, z) =√2pc(x, y) G(x, z) pk(x)+G(y, z) pk(y)−pk(z) 4vol(Γ)!, GS(vxy, vzt) =pc(x, y)c(z, t) G(x, z) pk(x)k(z)+G(x, t) pk(x)k(t)+G(y, z) pk(y)k(z)+G(y, t) pk(y)k(t) ! −3pc(x, y)c(z, t) 2vol(Γ) +εvzt (vxy). 4.2. Subdivision networks for the normalized Laplacian 55 Proof. For the first case, suppose z∈V, and let hz=εz−pkS(z) 4vol(Γ) √kS. After Theorem 4.2.1, for every x∈Vthe data function to be used for the Poisson problem on Γmust be hz(x) = εz(x)−pkS(z)pkS(x) 4vol(Γ) −1 √2pkS(z) 4vol(Γ) X y∼xpc(x, y) pk(x)qkS(vxy) =εz(x)−pkS(x)pkS(z) 2vol(Γ) =εz(x)−pk(x)pk(z) vol(Γ) . The unique solution to the Poisson problem L(uz)=2hz,orthogonal to √k, using the Green function for Γ, is uz(x)=2G(x, z), and from Corollary 4.3.2 GS(x, z) = 2G(x, z) + pk(x)pk(z) 4vol(Γ)2X r∼sqkS(vrs)pc(r, s) = 2G(x, z) + pk(x)pk(z) 2vol(Γ)2X r∼s c(r, s)=2G(x, z) + pk(x)pk(z) 4vol(Γ) . On the other hand, for every vxy ∈V0, GS(vxy, z) = √2pc(x, y) G(x, z) pk(x)+G(y, z) pk(y)! −pk(z)pc(x, y) √2vol(Γ) +pc(x, y)pk(z) √2vol(Γ)2X r∼s c(r, s) =√2pc(x, y) G(x, z) pk(x)+G(y, z) pk(y)−pk(z) 4vol(Γ)!. Finally, we complete the proof by considering the case where the pole is a new generated vertex by the subdivision procedure. So suppose now vzt ∈V0, and let hvzt =εvzt −pc(z, t) 2vol(Γ) √kS.Then, for every x∈V 62 Chapter 4. Subdivision networks GS q0(vxy, z) = α(x, y)Gqω(x, z) + α(y, x)Gqω(y, z) −X `∈V ωS(z)α(x, y)Gqω(x, `) + α(y, x)Gqω(y, `)πS(`) −X `∈V ωS(vxy)Gqω(z, `)πS(`) +β−c(x, y) c(x, vxy)c(y, vxy)ωS(vxy)ωS(z), GS q0(vxy, vzt) = εzt(vxy)c(x, y) c(x, vxy)c(y, vxy) +ωS(vzt)ωS(vxy)β−c(x, y) c(x, vxy)c(y, vxy)−c(z, t) c(z, vzt)c(t, vzt) −ωS(vzt)X `∈Vα(x, y)Gqω(x, `) + α(y, x)Gqω(y, `)πS(`) −ωS(vxy)X `∈Vα(z, t)Gqω(z, `) + α(t, z)Gqω(t, `)πS(`) +α(x, y)α(z, t)Gqω(x, z) + α(t, z)Gqω(x, t) +α(y, x)α(z, t)Gqω(y, z) + α(t, z)Gqω(y, t). Proof. Suppose z∈V, and let hz=εz−ωS(z)ωS.Then, for every x∈V hz(x) = εz(x)−ωS(x)ωS(z)−X y∼N(x) α(x, y)ωS(vxy)ωS(z) =εz(x)−ωS(x)ωS(z)−X y∼N(x) c(x, vxy)ωS(z)ωS(vxy)2 c(x, vxy)ω(x) + c(y, vxy)ω(y) =εz(x)−ωS(x)ωS(z)−ωS(z)X y∼N(x) c(x, y)ωS(vxy) c(y, vxy) =εz(x)−(ωS(x) + πS(x))ωS(z), with πS(x) = X y∼N(x) c(x, y)ωS(vxy) c(y, vxy). Hence, from Theorem 4.3.1, the related Poisson problem to solve on Γis Lqω(uz) = hzand, using the Green kernel Gfor Γ,we obtain uz(x) = Gqω(εz)(x)−X `∈V Gqω(x, `)πS(`)ωS(z) =Gqω(x, z)−X `∈V Gqω(x, `)πS(`)ωS(z). 4.3. Partial subdivision for singular Schrödinger type operators 63 Hence, after corollary 4.3.2 the expression of the Green kernel on ΓSis GS q0(vxy, z) = h(vxy)c(x, y) c(x, vxy)c(y, vxy)+α(x, y)u(x) + α(y, x)u(y) −X {r,s}∈E1 c(r, s)ωS(vrs) c(r, vrs)c(s, vrs)h(vrs)ωS(vxy) −X {r,s}∈E1 c(r, s)ωS(vrs) c(r, vrs)c(s, vrs)(c(r, vrs)u(r) + c(s, vrs)u(s)) ωS(vxy). After substituting, our expression turns to be GS q0(vxy, z) = −ωS(vxy)ωS(z)c(x, y) c(x, vxy)c(y, vxy)+α(x, y)Gqω(x, z) + α(y, x)Gqω(y, z) −ωS(z)P `∈Vα(x, y)Gqω(x, `) + α(y, x)Gqω(y, `)πS(`) +ωS(z)X {r,s}∈F c(r, s)ωS(vrs) c(r, vrs)c(s, vrs)ωS(vrs)ωS(vxy) −X {r,s}∈E1 c(r, s)ωS(vrs) c(r, vrs)c(s, vrs)(c(r, vrs)Gqω(r, z)) ωS(vxy) −X {r,s}∈E1 c(r, s)ωS(vrs) c(r, vrs)c(s, vrs)(c(s, vrs)Gqω(s, z)) ωS(vxy) +X {r,s}∈E1 c(r, s)ωS(vrs) c(s, vrs) X `∈V Gqω(r, `)πS(`)ωS(z)!ωS(vxy) +X {r,s}∈E1 c(r, s)ωS(vrs) c(r, vrs) X `∈V Gqω(s, `)πS(`)ωS(z)!ωS(vxy) and can finally can be established as GS q0(vxy, z) = −ωS(vxy)ωS(z)c(x, y) c(x, vxy)c(y, vxy)+α(x, y)Gqω(x, z) + α(y, x)Gqω(y, z) −X `∈V ωS(z)α(x, y)Gqω(x, `) + α(y, x)Gqω(y, `)πS(`) −X `∈VωS(vxy)Gqω(z, `)πS(`) +ωS(z)ωS(vxy)X {r,s}∈E1 c(r, s)ωS(vrs) c(r, vrs)c(s, vrs)ωS(vrs) +ωS(z)ωS(vxy)X r,`∈V Gqω(r, `)πS(`)πS(r). 64 Chapter 4. Subdivision networks On the other hand, for vertices from former structure GS q0(x, z) = uhz z(x)−X {r,s}∈E1 c(r, s)ωS(vrs) c(r, vrs)c(s, vrs)h(vrs)ωS(x) −X {r,s}∈E1 c(r, s)ωS(vrs) c(r, vrs)c(s, vrs)c(r, vrs)u(r) + c(s, vrs)u(s)ωS(x). This expression can be seen as GS q0(x, z) = Gqω(x, z)−X `∈V Gqω(x, `)πS(`)ωS(z) +ωS(x)ωS(z)X {r,s}∈E1 c(r, s)ωS(vrs)2 c(r, vrs)c(s, vrs) −X {r,s}∈E1 α(r, s)Gqω(r, z)ωS(vrs)ωS(x) +X {r,s}∈E1 α(r, s) X `∈V Gqω(r, `)πS(`)ωS(z)!ωS(vrs)ωS(x) −X {r,s}∈E1 α(s, r)Gqω(s, z)ωS(vrs)ωS(x) +X {r,s}∈E1 α(s, r) X `∈V Gqω(s, `)πS(`)ωS(z)!ωS(vrs)ωS(x). Finally, by summing up related terms, we obtain the desired expression GS q0(x, z) = Gqω(x, z)−ωS(x)ωS(z)X `∈VhGqω(x, `) ωS(x)+Gqω(z, `) ωS(z)iπS(`) +ωS(x)ωS(z)X r,s∈V Gqω(s, r)πS(r)πS(s) +ωS(x)ωS(z)X {r,s}∈E1 c(r, s)ωS(vrs)2 c(r, vrs)c(s, vrs). Once the first case is completed, suppose now vzt ∈V0,and consider as data function hvzt =εvzt −ωS(vzt)ωS.Then, for every x∈Vthe corresponding contraction results in hvzt (x) = εvzt (x)−ωS(vzt)ωS(x) +X y∈S(x) α(x, y)εvzt (vxy)−ωS(vzt)ωS(vxy). This previous expression can be developed and finally rewritten as follows 4.3. Partial subdivision for singular Schrödinger type operators 65 hvzt (x) = −ωS(vzt)ωS(x) + X y∈S(x) α(x, y)εvzt (vxy)−ωS(vzt)ωS(vxy) =−ωS(vzt)ωS(x) + X y∈S(x) α(x, y)εvzt (vxy) −ωS(vzt)X y∈S(x) α(x, y)ωS(vxy) =−ωS(vzt)ωS(x) + α(z, t)εz(x) + α(t, z)εt(x)−ω(vzt)πS(x) =−ωS(vzt)ωS(x) + πS(x)+α(z, t)εz(x) + α(t, z)εt(x). Hence, the Poisson problem to solve on Γis stated as Lqω(uvzt ) = hvzt .Its solution, by using Green’s kernel for Γ,is uvzt (x) = −ωS(vzt)X `∈V Gqω(x, `)ω(`) + πS(`) +α(z, t)Gqω(x, z) + α(t, z)Gqω(x, t) =−ωS(vzt)P `∈V Gqω(x, `)πS(`) + α(z, t)Gqω(x, z) + α(t, z)Gqω(x, t). Then, the result follows by applying once again Corollary 4.3.2. GS vzt (vxy) = hzt(vxy)c(x, y) c(x, vxy)c(y, vxy)+α(x, y)uzt(x) + α(y, x)uzt(y) −X {r,s}∈F c(r, s)ωS(vrs) c(r, vrs)c(s, vrs)hzt(vrs)ω(vxy) −X {r,s}∈F c(r, s)ωS(vrs) c(r, vrs)c(s, vrs)(c(r, vrs)uzt(r) + c(s, vrs)uzt(s)) ω(vxy) GS vzt (vxy) = εzt(vxy)c(x, y) c(x, vxy)c(y, vxy)−ω(vzt)ω(vxy)c(x, y) c(x, vxy)c(y, vxy) −ω(vzt)X `∈Vα(x, y)G(x, `) + α(y, x)G(y, `)πS(`) +α(x, y)α(z, t)G(x, z) + α(x, y)α(t, z)G(x, t) +α(y, x)α(z, t)G(y, z) + α(y, x)α(t, z)G(y, t) −X {r,s}∈F c(r, s)ωS(vrs) c(r, vrs)c(s, vrs)(εvzt (vrs)−ω(vzt)ω(vrs)) ω(vxy) −X {r,s}∈F c(r, s)ωS(vrs) c(r, vrs)c(s, vrs)(c(r, vrs)uzt(r)) ω(vxy) −X {r,s}∈F c(r, s)ωS(vrs) c(r, vrs)c(s, vrs)(c(s, vrs)uzt(s)) ω(vxy). 66 Chapter 4. Subdivision networks Now substituting the values of the solution of the Poisson problem on Γ,the expression becomes GS vzt (vxy) = εzt(vxy)c(x, y) c(x, vxy)c(y, vxy)−ω(vzt)ω(vxy)c(x, y) c(x, vxy)c(y, vxy) −ω(vzt)X `∈Vα(x, y)G(x, `) + α(y, x)G(y, `)πS(`) +α(x, y)α(z, t)G(x, z) + α(x, y)α(t, z)G(x, t) +α(y, x)α(z, t)G(y, z) + α(y, x)α(t, z)G(y, t) −c(z, t)ωS(vzt)ω(vxy) c(z, vzt)c(t, vzt)+ω(vzt)ω(vxy)X {r,s}∈F c(r, s)ωS(vrs)2 c(r, vrs)c(s, vrs) +X {r,s}∈F c(r, s)ωS(vrs) c(s, vrs) −ω(vzt)X `∈V G(r, `)πS(`)!ω(vxy) −X {r,s}∈F c(r, s)ωS(vrs) c(s, vrs)(α(z, t)G(r, z) + α(t, z)G(r, t)) ω(vxy) +X {r,s}∈F c(r, s)ωS(vrs) c(r, vrs) −ω(vzt)X `∈V G(s, `)πS(`)!ω(vxy) −X {r,s}∈F c(r, s)ωS(vrs) c(r, vrs)(α(z, t)G(s, z) + α(t, z)G(s, t)) ω(vxy). A little more development of the expression turns to GS vzt (vxy) = εzt(vxy)c(x, y) c(x, vxy)c(y, vxy)−ω(vzt)ω(vxy)c(x, y) c(x, vxy)c(y, vxy) −ω(vzt)X `∈Vα(x, y)G(x, `) + α(y, x)G(y, `)πS(`) +α(x, y)α(z, t)G(x, z) + α(x, y)α(t, z)G(x, t) +α(y, x)α(z, t)G(y, z) + α(y, x)α(t, z)G(y, t) +ω(vzt)ω(vxy)X {r,s}∈F c(r, s)ωS(vrs)2 c(r, vrs)c(s, vrs) +X r,`∈V G(r, `)πS(`)πS(r)ω(vzt)ω(vxy) −X r∈F (α(z, t)G(r, z) + α(t, z)G(r, t)) πS(r)ω(vxy). 4.3. Partial subdivision for singular Schrödinger type operators 67 And finally we complete the proof by writting GS vzt (vxy) = εzt(vxy)c(x, y) c(x, vxy)c(y, vxy)+ωS(vzt)ω(vxy)β −ωS(vzt)ω(vxy)c(x, y) c(x, vxy)c(y, vxy)+c(z, t) c(z, vzt)c(t, vzt) −X `∈V ω(vzt)α(x, y)G(x, `) + α(y, x)G(y, `)πS(`) −X `∈V ω(vxy)α(z, t)G(z, `) + α(t, z)G(t, `)πS(`) +α(x, y)α(z, t)G(x, z) + α(x, y)α(t, z)G(x, t) +α(y, x)α(z, t)G(y, z) + α(y, x)α(t, z)G(y, t). If we consider E1=E; that is, the case of subdivision networks, the above result coincides except for a constant with [26, Proposition 3.1]. The scalar is due to the fact that in the mentioned work, we were considering no weights in the vertex set; i.e.,ω(x)=1for any x∈Vand hence the normalization factor appears. 5 Resistance Distance and Kirchhoff Index. The concept of distance is a basic one in the whole human experience. In every day life, it usually means some degree of closeness of two physical objects or ideas, i.e. length, time interval, gap, rank difference, coolness or remoteness, while the term metric is often used as a standard for a measurement. The mathematical notions of (i) distance metric ( i.e. a nonnegative function d(x, y)that vanishes only when x=y, symmetric and that fulfills the so called triangular inequality d(x, y)≤d(x, z) + d(z, y)), and of (ii) metric space, were originated a little over a century ago by M. Fréchet 1and F. Hausdorff2even though the triangle inequality above appears in Euclid. Distances and metrics have become now an essential tool in many areas of mathematics and its applications including geometry, probability, statistics, coding/graph theory, clustering, data analysis, pattern recognition, networks, engineering, computer graphics/vision, astronomy, cosmology, molecular biology, and many others areas of science. Devising the most suitable distance metric and similarities, in order to quantify the proximity between objects, has become a standard task for many researchers. Especially intense ongoing search for such distances occurs in so many and diverse areas as for example computational biology, image analysis, speech recognition and information retrieval, just to mention a few. Canonical geodesic distance on graphs is probably the most ancient, natural and used notion of distance on discrete structures and has proved to be very suitable for dealing with so many situations and purposes of great interest. But also shows its limitations when the phenomena that is being studied 1In 1906, Maurice Fréchet submitted his outstanding thesis Sur Quelques points du Calcul Fonctionnel introducing (within a systematic study of functional operation) the notion of metric space (E-espace, E from écart in french, which means gap). 2In 1914, Felix Hausdorff published his famous Grundzüge der Mengen–Lehre where the theory of topological and metric spaces (metrische Räume) was created. 70 Chapter 5. Resistance Distance and Kirchhoff Index. is considered to be transmitted in a quite more sophisticated way as when the framework is that of virus diseases or social media or electrical circuits for instance. Due to the own nature of whatever is propagating, it does not take place by solely using one option (the shortest path) but all possibilities are taken into account. Hence looking for new alternatives to this distance concept is justified. Klein and Randic’s 1993 electrical idea of effective resistances, see [58], is then a different paradigm that has shown its versatility and opportunity to deal with these situations. This is verified not only because of the big amount of bibliographic references that the mathematical community is generating more and more and progressively, but also because, and very interestingly, the same distance metric appeared independently and in the apparently very poorly related framework of social media in Stephenson and Zeller, [70]. It is quite often that a result or an idea is found in different areas, but this happy coincidence reaffirms the importance and opportunity of the discovery. Equivalance between apparentely different distances is stated in [18, 37], for example. Another concern of major interest in the study of discrete structures is the obtention of topological indices. Graphs and networks do have properties that are very useful when unravelling the information that they contain, so it is very interesting to extract meaningful information that you would not have if the individual components were examined separately with all the complexity of the whole vertices and edges set. In this sense, several measures of network performance, topological indices and classification parameters have been introduced and studied. The way in which the nodes and edges are arranged within a discrete structure is its particular topology and can help us to identify relevant aspects of it. Topological properties can apply to the network as a whole or to individual nodes and edges, they are of a great nature of origins and some of them, just to put a few examples, are the degree and the centrality of a vertex, the degree distribution (that defines whether a network is scale–free or not), the diameter of the whole structure, the closeness and betweenness concepts, . .. Perhaps the best known and most widely used topological index is the Wiener index which is based on the geodesic distance of vertices. It was defined and used by Wiener in 1947 when comparing the boiling points of some alkane isomers. Since then, over 3000 topological graph indices are registered including Hosoya index, Estrada index, Randič connectivity index, Zabreg group for instance. There is also a rapidly increasing interest in this topic, therefore topological graph indices are researched worldwide in so many scientific diverse areas. 5.1. Resistance distance or effective resistance 71 In this sense there are many proposals that have proven their opportunity and raison d’être and that are worth analyzing. Among them the Kirchhoff index is a global parameter that is tested day by day as really suitable. The Kirchhoff index topologically analyzes the structure, initially from the point of view of its global connectivity but also, and more lately, for centrality concerns (as those of closeness and betweenness just mentioned) as well. An interpretation that is usually given for the Kirchhoff index is as a generalization of the former Wiener index when resistance distances are considered in a discrete structure instead of the primitive geodesic shortest path distance. Therefore, we will devote this chapter to these two topics: resistance distances and Kirchhoff index. After a very brief introduction of both concepts, we will develop a more detailed exposition of them, how they are considered and computed, whenever the structure in which they are defined turns more elaborated from time to time, it is for graph, for networks and finally in a Schödinger type operator setting. Finally we obtain resistance distances and Kirchhoff index for subdivision networks in the three different scenarios we are treating in this thesis, relating them to their correspondents on the former discrete structure, the one existing previously to the subdivision procedure. To be honest, all these results are obtained after Green’s function for the adequately stated Poisson problem as mere by–products. Even though they are very important results in some specific areas on discrete structures or network science, the power of discrete potential theory allows the obtention of them quite straightforward. 5.1 Resistance distance or effective resistance Geodesic distance is enough for in some environments, but it is clearly unsatisfactory in many other more, when information, current, whatever is distributed within a discrete structure is more properly assumed to be diffused not only in a “shortest” way, but in all possible ways (as do fluids on the air for instance). The geodesic distance between two nodes does not consider the actual number of (shortest) paths that lie among the two vertices: two nodes that are separated by a single path are at the same distance than two nodes that are separated by many more paths of the same length. In many applications, however, paths longer than geodesic ones are also relevant, since information or whatever flows on the network does not necessarily choose an optimal path. For instance, in social networks, a fad does not know the optimal route to move among actors, but simply wanders around more or less randomly; moreover, nodes separated by many pathways are often perceived closer than nodes separated by few pathways, even if the paths have all the same length. Communication between nodes is typically enhanced as soon as more routes 78 Chapter 5. Resistance Distance and Kirchhoff Index. paper the authors relate equilibria measures associated with the combinatorial Laplacian kernel and the corresponding Wiener capacities, a powerful idea when the structure is symmetric. The authors also generalize Palacio’s techniques, [69]. As in the former standard setting, the effective resistance between vertices xand ycan also be defined through the solution of the Poisson problem L(u) = fwhen the data function is the dipole with poles at xand at y; that is f=εx−εy.Being data f∈ C(V),so that the corresponding Poisson problem is compatible, the effective resistance is defined as R(x, y) = u(x)−u(y) with u∈ C(V)is any solution, no matter what. We remark that R(x, y)is independent on the chosen solution u. Again the Kirchhoff index or Total resistance of a network is k(Γ) = 1 2X x,y∈V R(x, y). Effective resistances can be used to deduce important properties of electrical networks as can be seen in [50, 58, 74]. Also a couple of good references where some calculations have been developed are [5, 8]. 5.5 Resistance distances and Kirchhoff index for Schrödinger operators In [9] a generalization of the concept of effective resistance with respect to a value λ≥0and a weight ω∈Ω(V)was introduced through a commonly used technique in the context of electrical networks and Markov chains and with the aim of generalizing the Fiedler characterization of irreducible, symmetric and diagonally dominant M–matrices as resistive inverses, see [46], to all irreducible and symmetric M–matrices or equivalently, to all positive semi– definite Schrödinger operators. This generalization is essential to obtain the expression for the Kirchhoff index of a composite network in terms of the Kirchhoff indexes of the factors, see [1, 2]. When associating a positive value to each node of a network and then defining a one parametric family of resistance distances associated with this weight function through a positive semi–definite Schrödinger type operator (for which the parameter and the function are the lowest eigenvalue and the corresponding eigenfunction), the framework of discrete potential theory is applicable to analyze the main properties of these distances. 5.5. Resistance distances and Kirchhoff index for Schrödinger operators 79 This generalized effective resistance, with respect to λand ω, define a distance on the network as in the standard case and hence it can be also used with the same aims, see [14]. Actually we will explain how the effective resistance verifies analogous properties to those that the classical case satisfy. Among them, the relation between the Kirchhoff index with respect to λand ωand the eigenvalues of the associated Schrödinger operator as well as the relation between the effective resistances with respect to λand ωand the eigenvalues and eigenfunctions of the mentioned operator. Specifically, given λ≥0and ω∈Ω(V)so that q=qω+λ, the ω–dipole function with poles at xand yis defined as f=1 ω(εx−εy).Clearly P(f) = 0so the Poisson problem Lq(u) = fis consistent. Moreover every one of its solutions maximizes the functional Ix,y(u) = 2hu(x) ω(x)−u(y) ω(y)i−hLq(u, u)i. Then given x, y ∈V, the generalization of the effective resistance is defined, with respect to λand ωso that Rλ,ω(x, y) = max u∈C(V){Ix,y(u)}. Since the matrix associated with the Schrödinger operator Lqis an irreducible, symmetric M–matrix, and conversely, every irreducible, symmetric M–matrix appears as associated with a Schrödinger operator, we can assign an effective resistance function to any irreducible, symmetric M–matrix (not necessarily diagonally–dominant). Hence, the generalized Kirchhoff index of Γwith respect to λand ωis k(λ, ω) = 1 2X x,y∈V Rλ,ω(x, y)ω2(x)ω2(y). Observe that, our definitions of effective resistance and Kirchhoff index when ωis constant, differ from the classical ones in a factor of |V|, since the weight is always normalized to 1. As we will see for us the Kirchhoff index is basically the trace of the Green function, giving to that index a physical meaning. Also note, that the defined Kirchhoff index can be seen as one half of the energy of the kernel given by the effective resistance matrix applied to the vector ωand finally, R0,1(x, y) = R(x, y). Nevertheless, the calculation of Rλ,ω(x, y)is again in terms of the solution of a Poisson problem with the ω–dipole function as data function, as can be seen in [9]. Moreover, symmetry, non–negativity and relationship with the Green kernel function is also obtained from the fact that, for u∈ C(V)any 80 Chapter 5. Resistance Distance and Kirchhoff Index. solution of the Poisson equation Lq(u) = f, then Rλ,ω(x, y) = hLq(u), ui=u(x) ω(x)−u(y) ω(y). . From this expression, Rλ,ω is symmetric, non–negative and vanishes if and only if x=y. In addition, Rλ,ω(x, y) = Gq(x, x) ω2(x)+Gq(y, y) ω2(y)−2Gq(x, y) ω(x)ω(y). So, the role of the Green function is crucial in order to evaluate effective resistances and the subsequent Kirchhoff index of the network as k(λ, ω) = X x∈V Gq(x, x)−λ†. where λ†=λ−1if λ > 0and λ†= 0 if λ= 0.We see from the above expression that the Kirchhoff index is the trace of the Green function. The main properties satisfied by this generalized effective resistance may be are those listed in the next final result, see [24]. Theorem 5.5.1. If Γis a connected network, the effective resistance with respect to a parameter and a weight satisfies the following properties: 1. The effective resistance Rλ,ω(x, y)determines a distance on the network. Moreover, Rλ,ω(x, y) = Rλ,ω(x, z) + Rλ,ω(z, y)if and only if λ= 0 and zseparates xand y. 2. For 0≤ˆ λ≤λand ˆq=qω+ˆ λthen Rλ,ω ≤Rˆ λ,ω ≤R0,ω. 3. Rλ,ω(x, y)≤dˆc(x, y),where ˆc(x, y) = c(x, y)ω(x)ω(y),with equality if and only if λ= 0 and there exists a unique path from xto y. 4. lim λ→+∞Rλ,ω = 0 and lim λ→0Rλ,ω =R0,ω. Or in other words, for a fixed weight function ω, the associated effective resistance distances are continuous and monotone decreasing with respect to the parameter λ(the larger the parameter, the lower the resistance) and they are upper bounded by the weighted geodesic distance of the network. Moreover, both distances do coincide if and only if the parameter is null and the network is a tree. In addition, this new generalized resistance distance is graph geodetic if and only if the operator is singular. Just to end this section we mention that in the case of constant weight, by applying some electrical equivalences it is possible to show that the one– parametric family of effective resistances can be seen as the effective resistance associated with the combinatorial Laplacian of a complete network. The so called forest distance and adjusted forest distance can be recovered as this particular case, see [30]. 5.6. Resistance distances and Kirchhoff index on subdivision networks 81 5.6 Resistance distances and Kirchhoff index on subdivision networks After this presentation of both treated concepts and their different interpretation and computation depending on the case we are considering, we are now in a position to present our results when electrical subdivision of a network is considered. Of course we did our job in the three, at this point, well known cases we are considering in this manuscript: standard electrical subdivision for a combinatorial Laplacian operator, also standard electrical subdivision for a normalized Laplacian operator and finally the third a more general case of partial electrical subdivision for a Schrödinger type operator. What it follows, structured in subsections, are the corresponding results we have obtained in every case. Hence this section mimics previous sections of Chapter 3. 5.6.1 Subdivision for combinatorial Laplacian We are now concerned with the relation between effective resistances in a base network Γand the effective resistances, RS, in a subdivision network ΓS. Theorem 5.6.1. Let Γ = (V, E, c)be a network and ΓS= (VS, ES, c)its subdivision network, then RS(x, y) = R(x, y), RS(x, vzt) = 1 k(vzt)+α(z, t)R(x, z) + α(t, z)R(x, t)−α(z, t)α(t, z)R(z, t), RS(vxy, vzt) = 1 k(vxy)+1 k(vzt) −α(x, y)α(y, x)R(x, y)−α(z, t)α(t, z)R(z, t) +α(x, y)α(z, t)R(x, z) + α(x, y)α(t, z)R(x, t) +α(z, t)α(y, x)R(y, z) + α(y, x)α(t, z)R(y, t),for vxy 6=vzt. Proof. The proof is a direct consequence of Proposition 4.3.3. Let us do the non–trivial case 2. The case 3, can be proved similarly. RS(x, vzt) = GS(x, x) + GS(vzt, vzt)−2GS(x, vzt) 82 Chapter 5. Resistance Distance and Kirchhoff Index. RS(x, vzt) = G(x, x)−2 n+mX `∈V G(x, `)πS(`) +α(z, t)α(z, t)G(z, z) + α(t, z)G(t, z)+ +α(t, z)α(z, t)G(z, t) + α(t, z)G(t, t) −2 n+mX `∈Vhα(z, t)G(z, `) + α(t, z)G(t, `)iπS(`) + εvzt (vzt) k(vzt) −2 (n+m)k(vzt)−2α(z, t)G(z, x)−2α(t, z)G(t, x) +2 n+mX `∈Vhα(z, t)G(z, `) + α(t, z)G(t, `) + G(x, `)iπS(`) +2 (n+m)k(vzt) RS(x, vzt) = 1 k(vzt)+G(x, x)−2α(z, t)G(z, x)−2α(t, z)G(t, x) +α(z, t)α(z, t)G(z, z) + α(t, z)G(t, z) +α(t, z)α(z, t)G(z, t) + α(t, z)G(t, t) =1 k(vzt)+α(z, t)hG(x, x) + G(z, z)−2G(x, z)i +α(t, z)hG(x, x) + G(t, t)−2G(x, t)i −α(t, z)α(z, t)hG(z, z) + G(t, t)−2G(z, t)i, and hence, the result follows. Observe that the effective resistance between vertices of the original network remains unchanged, as expected. In particular for the standard subdivision graph we get the following result, which coincides with the obtained in [32, 71, 76], up to the factor 2 due to our (electrically compatible)–choice of the conductances. Corollary 5.6.2. Let Γ = (V, E, c)be a network and ΓS= (VS, ES, c)its standard subdivision network, then RS(x, y) = R(x, y), RS(x, vzt) = 1+2R(x, z)+2R(x, t)−R(z, t) 4, RS(vxy, vzt) = 2−R(x, y)−R(z, t) + R(x, z) + R(x, t) + R(y, z) + R(y, t) 4, for any vxy 6=vzt. 5.6. Resistance distances and Kirchhoff index on subdivision networks 83 Next we obtain an expression for the Kirchhoff index of the subdivision network, k(ΓS), in terms of the Kirchhoff index, k, of the base network and other parameters. Theorem 5.6.3. Let Γ = (V, E, c)be a network and ΓS= (VS, ES, c)its subdivision network, then k(ΓS) = n+m nk(Γ) + (n+m)X x∈V G(x, x)πS(x)−X x,y∈V G(x, y)πS(x)πS(y) −(n+m)X x∼y α(x, y)α(y, x)R(x, y)+(n+m−1) X x∼y 1 k(vxy). Proof. k(ΓS) = (n+m)X x∈V GS(x, x)+(n+m)X vxy∈V0 GS(vxy, vxy) =(n+m) nk(Γ) −2X x∈VX `∈V G(x, `)πS(`) + (n+m)X vxy∈V0 α(x, y)2G(x, x)+2α(x, y)α(y, x)G(y, x)+α(y, x)2G(y, y) −2X vxy∈V0X `∈Vhα(x, y)G(x, `) + α(y, x)G(y, `)iπS(`) +X x,y∈V G(x, y)πS(x)πS(y)+(n+m−1) X x∼y 1 k(vxy) kS=n+m nk(Γ) + (n+m)X x,y∈Vα(x, y)2G(x, x) + α(x, y)α(y, x)G(y, x) −X x,y∈V G(x, y)πS(x)πS(y)+(n+m−1) X x∼y 1 k(vxy) =n+m nk(Γ) + (n+m)X x∈V G(x, x)πS(x)−(n+m)X x∼y α(x, y)α(y, x)R(y, x) −X x,y∈V G(x, y)πS(x)πS(y)+(n+m−1) X x∼y 1 k(vxy). In particular, the Kirchhoff index of the standard subdivision graph has the following expression which, coincides with [71, Th 3.1]. In the case of k–regular graph the result coincides with [49, Th 3.5]. Corollary 5.6.4. Let ΓSbe the standard subdivision network of a graph Γ; then k(ΓS) = n+m nk(Γ) + (n+m)X x∈V G(x, x)πS(x)−X x,y∈V G(x, y)πS(x)πS(y) +m2−n2+n 4. 84 Chapter 5. Resistance Distance and Kirchhoff Index. In particular, if Γis k–regular k(ΓS) = (k+ 2)2 4k(Γ) + (k2−4)n2+ 4n 16 . 5.6.2 Subdivision for the normalized Laplacian From Theorem 4.2.3, we easily calculate the values of the effective resistances for the subdivision network. Moreover, we also give the expression of its Kirchhoff index. Theorem 5.6.5. Let ΓSbe the subdivision network of Γ, then for any x, z ∈V and vxy, vzt ∈V0, the effective resistances between vertices of ΓSare given by RS(x, z) = R(x, z), RS(vxy, z) = 1 4 1 c(x, y)+1 2R(x, z) + 1 2R(y, z)−1 4R(x, y), RS(vxy, vzt) = 1 41 c(x, y)+1 c(z, t) +1 4R(x, z) + R(x, t) + R(y, z) + R(y, t)−R(x, y)−R(z, t), for any vxy 6=vzt. Moreover, the Kirchhoff index of the subdivision network is k(ΓS) = 16 k(Γ) + 2 vol(Γ)(2m−2n+ 1). Proof. The expressions for the effective resistance follow directly from Theorem 4.2.3 and Proposition 4.3.3. On the other hand, from the definition of Kirchhoff index we get k(ΓS) =8k(Γ) + 2vol(Γ)(2m−1) +4vol(Γ) X x∼y c(x, y) G(x, x) k(x)+2 G(x, y) pk(x)k(y)+G(y, y) k(y)! =8k(Γ) + 2vol(Γ)(2m−1) +4vol(Γ) X x∈V G(x, x) k(x)X y∼x c(x, y) +4vol(Γ) X x∈V 1 pk(x)X y∼x c(x, y)G(x, y) pk(y) =12k(Γ) + 2vol(Γ)(2m−1) + 4vol(Γ) X x∈V G(x, x) k(x)X y∼x c(x, y) +4vol(Γ) X x∈V 1 pk(x)X y∼x c(x, y) G(x, y) pk(y)−G(x, x) pk(x)! =16k(Γ) + 2vol(Γ)(2m−1) −4vol(Γ) X x∈V 1−pk(x) vol(Γ) pk(x)! =16k(Γ) + 2vol(Γ)(2m−2n+ 1). 5.6. Resistance distances and Kirchhoff index on subdivision networks 85 5.6.3 Partial Subdivision for Schrödinger operator In this section we aim at obtaining the expression for the effective resistances on a partial subdivision network of a given network Γ. The expression will follow by taking into account the expression for the effective resistances in terms of Green’s function. Proposition 5.6.6. Let ΓSbe a partial subdivision network of Γ, then for any x, z ∈Vand vxy, vzt ∈V0, the effective resistances of ΓSare given by RS ωS(x, z) = 1 α2Rω(x, y), RS ωS(vzt, x) = c(z, t) α2c(z, vzt)c(t, vzt)ω(vzt)2 +ω(z)ω(t) α2ω(vzt)α(z, t)Rω(x, z) ω(t)+α(t, z)Rω(x, t) ω(z) −α(t, z)α(z, t)Rω(z, t) ω(vzt), RS ωS(vxy, vzt) = c(x, y) α2c(x, vxy)c(y, vxy)ω(vxy)2+c(z, t) α2c(z, vzt)c(t, vzt)ω(vzt)2 +1 α2ω(vxy)ω(vzt)hα(x, y)α(z, t)ω(x)ω(z)Rω(x, z) +α(x, y)α(t, z)ω(x)ω(t)Rω(x, t) +α(y, x)α(z, t)ω(y)ω(z)Rω(y, z) +α(y, x)α(t, z)ω(y)ω(t)Rω(y, t)i −α(x, y)α(y, x)ω(x)ω(y) α2ω(vxy)2Rω(x, y) −α(z, t)α(t, z)ω(z)ω(t) α2ω(vzt)2Rω(z, t),for any vxy 6=vzt. Proof. Suppose that x, z ∈V, then RS ωS(x, z) = GS q0(x, x) [ωS(x)]2+GS q0(z, z) [ωS(z)]2−2GS q0(x, z) ωS(x)ωS(z) =1 [ωS(x)]2Gqω(x, x)−2ωS(x)X `∈V Gqω(x, `)πS(`) +1 [ωS(z)]2Gqω(z, z)−2ωS(z)X `∈V Gqω(z, `)πS(`) −2 ωS(x)ωS(z)Gqω(x, z)−X `∈VωS(x)Gqω(z, `)+ωS(z)Gqω(x, `)πS(`)  =Gqω(x, x) [ωS(x)]2+Gqω(z, z) [ωS(z)]2−2Gqω(x, z) ωS(x)ωS(z)=1 α2Rω(x, z). 86 Chapter 5. Resistance Distance and Kirchhoff Index. Moreover, if x∈Vand vzt ∈V0, then RS q0(x, vzt) = GS q0(x, x) [ωS(x)]2+GS q0(vzt, vzt) [ωS(vzt)]2−2GS q0(x, vzt) ωS(x)ωS(vzt), where from Proposition 4.3.3 GS q0(x, x) ωS(x)2=Gqω(x, x) ωS(x)2−2 ωS(x)X `∈V Gqω(x, `)πS(`) + β, GS q0(vzt, vzt) ωS(vzt)2=c(z, t) c(z, vzt)c(t, vzt)ωS(vzt)2−2c(z, t) c(z, vzt)c(t, vzt) −2 ωS(vzt)X `∈Vα(z, t)Gqω(z, `) + α(t, z)Gqω(t, `)πS(`) +α(z, t)2Gqω(z, z)+2α(z, t)α(t, z)Gqω(z, t)+α(t, z)2Gqω(t, t) ωS(vzt)2 +β GS q0(vzt, x) ωS(vzt)ωS(x)=α(z, t)Gqω(z, x) + α(t, z)Gqω(t, x) ωS(vzt)ωS(x)−c(z, t) c(z, vzt)c(t, vzt)+β −X `∈Vα(z, t)Gqω(z, `) ωS(vzt)+α(t, z)Gqω(t, `) ωS(vzt)+Gqω(x, `) ωS(x)πS(`). Summing up RS ωS(x, vzt) = c(z, t) c(z, vzt)c(t, vzt)ωS(vzt)2+Gqω(x, x) ωS(x)2 +α(z, t)2Gqω(z, z) ωS(vzt)2+α(t, z)2Gqω(t, t) ωS(vzt)2 +2α(z, t)α(t, z)Gqω(z, t) ωS(vzt)2−2α(z, t)Gqω(z, x) + α(t, z)Gqω(t, x) ωS(vzt)ωS(x) =c(z, t) c(z, vzt)c(t, vzt)ωS(vzt)2 +Gqω(x, x) ωS(x)2α(z, t)ω(z) ω(vzt)+α(t, z)ω(t) ω(vzt) +Gqω(z, z) ωS(z)2α(z, t)ω(z) ω(vzt)−α(t, z)α(z, t)ω(z)ω(t) ω(vzt)2 +Gqω(t, t) ωS(t)2α(t, z)ω(t) ω(vzt)−α(t, z)α(z, t)ω(z)ω(t) ω(vzt)2 +2α(z, t)α(t, z)ω(z)ω(t) ωS(vzt)2 Gqω(z, t) ω(z)ω(t) −2α(z, t)ω(z) ωS(vzt) Gqω(z, x) ωS(x)ω(z)−2α(t, z)ω(t) ωS(vzt) Gqω(t, x) ωS(x)ω(t) =c(z, t) c(z, vzt)c(t, vzt)ωS(vzt)2+α(z, t)ω(z) α2ω(vzt)Rω(x, z) +α(t, z)ω(t) α2ω(vzt)Rω(x, t)−α(t, z)α(z, t)ω(z)ω(t) α2ω(vzt)2Rω(z, t). 5.6. Resistance distances and Kirchhoff index on subdivision networks 87 For the last case, take into account also that GS q0(vxy, vzt) ωS(vxy)ωS(vzt)=εzt(vxy)c(x, y) c(x, vxy)c(y, vxy)ωS(vxy)ωS(vzt) −c(x, y) c(x, vxy)c(y, vxy)+c(z, t) c(z, vzt)c(t, vzt) −X `∈V α(x, y)G(x, `) + α(y, x)G(y, `) ωS(vxy) +α(z, t)G(z, `) + α(t, z)G(t, `) ωS(vzt) πS(`) +α(x, y)α(z, t)G(x, z) + α(x, y)α(t, z)G(x, t) ωS(vxy)ωS(vzt) +α(y, x)α(z, t)G(y, z) + α(y, x)α(t, z)G(y, t) ωS(vxy)ωS(vzt). Hence the expression for RS ωs(vxy, vzt)is RS ωs(vxy, vzt) = c(x, y) c(x, vxy)c(y, vxy)ωS(vxy)2+c(z, t) c(x, vzt)c(t, vzt)ωS(vzt)2 +α(x, y)2G(x, x)+2α(x, y)α(y, x)G(x, y) + α(y, x)2G(y, y) ωS(vxy)2 +α(z, t)2G(z, z)+2α(z, t)α(t, z)G(z, t) + α(t, z)2G(t, t) ωS(vzt)2 −2α(x, y)α(z, t)G(x, z) + α(x, y)α(t, z)G(x, t) ωS(vxy)ωS(vzt) −2α(y, x)α(z, t)G(y, z) + α(y, x)α(t, z)G(y, t) ωS(vxy)ωS(vzt) =c(x, y) c(x, vxy)c(y, vxy)ωS(vxy)2+c(z, t) c(x, vzt)c(t, vzt)ωS(vzt)2 +1 α2ωS(vxy)ωS(vzt) hα(x, y)α(z, t)ω(x)ω(z)R(x, z)+α(x, y)α(t, z)ω(x)ω(t)R(x, t) +α(y, x)α(z, t)ω(y)ω(z)R(y, z)+α(y, x)α(t, z)ω(y)ω(t)R(y, t)i −α(x, y)α(y, x)ω(x)ω(y) α2ωS(vxy)2R(x, y)−α(x, t)α(t, z)ω(z)ω(t) α2ωS(vzt)2R(z, t). Proposition 5.6.7. Let ΓSbe the partial subdivision network of Γ, then the Kirchhoff index of ΓSis given by k(ωS) = k(ω) + X x∈V πS(x) ωS(x)Gqω(x, x) + X {x,y}∈E1 c(x, y) c(x, vxy)c(y, vxy)−β +X {x,y}∈E1 α(x, y)α(y, x)ω(x)ω(y)Rω(x, y). 94 Chapter 6. Stars, Wheels When i=jwe get a similar expression GS ωS(x2i, x0 2i) = 1 2γ√2n+ 1G(x0, x2i) + G(x2i, x2i) −nα2γ3√2n+ 1 4G(x0, x0) + G(x2i, x0)+2G(x2i, x0) −α2γ3√2n+ 1 4 n X k=1 G(x0, x2k) + G(x2i, x2k)+2G(x2i, x2k) + n2α4γ4Q+α2γ4 2 n X k=1 1 ak−γ2(2n+ 1) 4 1 ai!α2γ √2n+ 1 =γ √2n+ 1 Q+γ(n−1) √2n+ 1 1 ai−nγ3α2 √2n+ 1 Q+3nγ3α2 4√2n+ 1 1 ai −nγ3α2 √2n+ 1 Q+γ3α2 √2n+ 1 n X k=1 1 ak−3(n+ 1)γ3α2 4√2n+ 1 1 ai + n2α4γ4Q+α2γ4 2 n X k=1 1 ak−γ2(2n+ 1) 4 1 ai!α2γ √2n+ 1 =α4γ √2n+ 1 Q+γ(4(n−1) −2(n+ 2)α2γ2) 4√2n+ 1 1 ai +α2γ3(2 + α2γ2) 2√2n+ 1 n X j=1 1 aj . For positions that involve only new vertices, we get GS ωS(x0 2i, x0 2j) = −α2γ4(2n+ 1) 41 ai +1 aj+βα2γ2 −nα2γ4(2n+ 1) 4(2G(x0, x0) + G(x2i, x0) + G(x2j, x0)) −α2γ4(2n+ 1) 4 n X k=1 (2G(x0, x2k) + G(x2i, x2k) + G(x2j, x2k)) +γ2(2n+ 1) 4(G(x0, x0) + G(x0, x2j) + G(x2i, x0) + G(x2i, x2j)) =−α2γ4(2n+ 1) 41 ai +1 aj+n2α4γ6Q+α4γ6 2 n X k=1 1 ak −nα2γ4 44Q−1 ai−1 ai−α2γ4 4 n X k=1 4Q−4 ak−1 ai−1 aj 6.1. Partial subdivision on star networks 95 −α2γ4(2n+ 1) 41 ai +1 aj+γ2 44Q−1 ai−1 aj =α4γ2Q−γ21+(n+ 1)α2γ2 21 ai +1 aj +α2γ4(2 + α2γ2) 2 n X k=1 1 ak . GS ωS(x0 2i, x0 2i) = γ2(2n+ 1) 4 1 ai−α2γ4(2n+ 1) 2 1 ai +βα2γ2 −nα2γ4(2n+ 1) 2(G(x0, x0) + G(x2i, x0)) −α2γ4(2n+ 1) 2 n X k=1 (G(x0, x2k) + G(x2i, x2k)) +γ2(2n+ 1) 4(G(x0, x0)+2G(x0, x2i) + G(x2i, x2i)) =γ2(2n+ 1) 4 1 ai−α2γ4(2n+ 1) 2 1 ai +n2α4γ6Q+α4γ6 2 n X k=1 1 ak −nα2γ4 44Q−2 ai −α2γ4 4 n X k=1 4Q−4 ak−2 ai−α2γ4(2n+ 1) 2ai +γ2 44Q−4 ai+γ2(2n+ 1) 4 1 ai =α4γ2Q−γ22n−1−2(n+ 1)α2γ2 2ai +α2γ4(2 + α2γ2) 2 n X k=1 1 ak . The remaining cases will follow by performing similar computations. Finally, we obtain the Kirchhoff index for the partial subdivision of the Star. Proposition 6.1.2. Let SS 2nbe the partial subdivision network of the star S2n, then the Kirchhoff index of SS 2nis given by kS ωS(SS 2n) = n(2 + α2γ2)Q+γ2 22n−1−α2γ2n X i=1 1 ai . Proof. Taking into account Proposition 5.6.7 kS ωS(SS 2n) = k(S2n) + X x∈V G(x, x)πS(x) ωS(x) −Px,y∈Fα(x, y)α(y, x)ωS(x)ωS(y)R(x, y) +X {x,y}∈E1 c(x, y) c(x, vxy)c(y, vxy)−β 96 Chapter 6. Stars, Wheels kS ωS(SS 2n) = 2nQ +nγ2 2Q+nγ2 2Q−γ2 n X i=1 1 ai +γ2 2(2n+ 1) n X i=1 1 ai −n2α2γ4Q−α2γ4 2 n X i=1 1 ai =2n+nγ2−n2α2γ4Q+γ2 2(2n−1−α2γ2) n X i=1 1 ai . As expected, the Kirchhoff Index of the partial subdivided Star takes the minimum value for γapproaching zero; this can be interpreted as no subdivision has been performed in the initial network S2n. Actually, kS ωS(SS 2n)attains a minimum for γ= 0. 6.2 Subdivision on Star networks for the normalized Laplacian In this section we add results corresponding to the case of the normalized Laplacian for subdivision on the n–Star, see [28]. Moreover, notice that in this case we do the subdivision process on every edge of the network. Firstly we consider the n–Star network, see Figure 6.2 (left), that has n+ 1 vertices, {x0, x1, . . . , xn}, and constant conductance a > 0,i.e.,c(x0, xi) = a, for i= 1, . . . , n, and zero otherwise. Thus, the degree function is k(x0) = na and k(xi) = afor i= 1, . . . , n, while vol(Γ) = 2na. Hence, the subdivision of the n– Star has nnew inserted vertices, those white in Fig. 6.2 (right), that we denote as vx0xi.Accordingly to the definition of the conductances, the degree function of the subdivision n–Star network is kS(x0) = 2na, kS(xi) = 2a, and kS(vx0xi) = 4a, i= 1, . . . , n. a a a 2a 2a 2a 2a Figure 6.2 The Star network and its subdivision network Normalized Laplacian matrices of the former network and its subdivision are, re- 6.2. Subdivision on Star networks for the normalized Laplacian 97 spectively L=    1−1 √n1T −1 √n1 I    and LS=         10T−1 √2n1T 0 I −1 √2I −1 √2n1−1 √2I I         being 0and 1, n entries vectors (all zeros, all ones) and Ithe n×nidentity matrix. It can be proved, see [23] for instance, that the group inverse matrix for such an n-Star network is G=    1 4−1 4√n1T −1 4√n1 A     being Aan n×nmatrix whose values are 1−3 4non the diagonal, and −3 4n otherwise. For the n–Star network, effective resistances are R(x0, xi) = 1 a, R(xi, xj) = 2 a, while its corresponding Kirchhoff index is k(Γ) = n(2n−1)a. Hence, using Proposition 4.3.3, we calculate GS=          5 8−3 8√n1T−√2 8√n1T −3 8√n1 A1A2 √2 8√n1 AT 2A3          where matrices A1,A2and A3have all the same “shape”; that is, a constant value on the diagonal and a different one off the diagonal, so they can be expressed in terms of the identity matrix and Jthe all ones matrix as A1= 2I−11 8nJ,A2=√2I−9√2 8nJand A3= 2I−7 4nJ. After using Proposition 5.6.6, effective resistances for the subdivision network of n–Star network are to be RS(x0, xi) = RS(vx0xi,x0xj) = 1 a, RS(x0, vx0xi) = RS(xi, vx0xi) = 1 2a, RS(xi, xj) = 2 aand RS(xi, vx0xj) = 3 2a, 98 Chapter 6. Stars, Wheels for i, j = 1, . . . , n, i 6=j. Please note that as the subdivided star is a tree, the values of the effective resistances do agree with those obtained by direct application of simple electrical properties. And also, the Kirchhoff index for the subdivision network of the n–Star network is, k(ΓS) = 4na(8n−5). a a a a c c c c 2a 2a 2c 2c 2c 2a 2c 2a 2a 2a Figure 6.3 The Wheel network and its subdivision network 6.3 Subdivision on Wheel networks for the normalized Laplacian In our second example, we consider the n–Wheel network, see Figure 6.3 (left), Wn, that has n+ 1 vertices labelled {x0, x1, . . . , xn}.The results in this section can be found in [25]. The only non null conductances are c(x0, xi) = a > 0and c(xi, xi+1) = c > 0, for i= 1, . . . , n, assuming xn+1 =x1.Thus, the degree function is defined as k(x0) = na and k(xi) = a+ 2cfor i= 1, . . . , n. In addition, vol(Wn)=2n(a+c). As the normalized Laplacian operator on a network can be seen as a particular Schrödinger operator, we use the results in [23] again to obtain the Green function of the normalized Laplacian for the n–Wheel network. And it is G(x0, x0) = (a+ 2c)2 (2(a+c))2 G(x0, xi) = −(a+ 2c)pna(a+ 2c) n(2(a+c))2, i = 1, . . . , n G(xi, xj) = −(a+ 2c)2 2na(a+c)a 2(a+c)+ 1+pUn−1−|i−j|(p) + U|i−j|−1(p) Tn(p)−1 i, j = 1, . . . , n, where p= 1 + a 2cand Tk(p)and Uk(p)are the first and the second kind Chebyshev polynomials respectively. 6.3. Subdivision on Wheel networks for the normalized Laplacian 99 Then the effective resistances are R(x0, xi) = n(a+c) c Un−1(p) (Tn(p)−1) R(xi, xj) = 2n(a+c) cUn−1(p) + Un−1−|i−j|(p) + U|i−j|−1(p) (Tn(p)−1) , i, j = 1, . . . , n, i 6=jand the Kirchhoff index is k(Wn) = 2n(a+c)−(a+ 2c)2 2a(a+c)+n(a+ 2c) 2c Un−1(p) Tn(p)−1 = 2n(a+c) p2 (2p−1)(1 −p)+ n−1 X j=0 p p−cos(2π j n) , taking into account that nUn−1(p) Tn(p)−1= n−1 X j=0 1 p−cos(2π j n). Let us now consider the subdivision network of the n–Wheel network. We denote the new white vertices in Figure 6.3 (right), by vx0xiand vxixi+1 ,i= 1, . . . , n provided xn+1 =x1,as before. According to the notation, the degree of the vertices in the subdivision network of the n–Wheel network are kS(x0)=2na,kS(xi) = 2(a+ 2c),kS(vx0xi)=4aand kS(vxixi+1 )=4c. From Proposition 4.3.3, we obtain the expression of the values of the Green function for the subdivision of the Wheel network case by case. Initially when only former vertices are concerned GS(x0, x0) = 5a2+ 17ac + 16c2 8(a+c)2, GS(x0, xi) = −pna(a+ 2c) 8n(a+c)2(3a+ 7c), i = 1, . . . , n; GS(xi, xj) = −(a+ 2c)2 8an(a+c)2(11a2+ 31ac + 16c2), + 2pUn−1−|i−j|(p) + U|i−j|−1(p) (Tn(p)−1) , i, j = 1, . . . , n. Secondly when both, former and later, kinds of vertices are involved for i, j = 100 Chapter 6. Stars, Wheels 1, . . . , n GS(x0, vx0xi) = √2 8√n 8c2+ 3ac −a2 (a+c)2; GS(x0, vxixi+1 ) = √2nac 8n(a+c)2(−5a−9c)assuming xn+1 =x1; GS(xj, vx0xi) = −p2a(a+ 2c) 8na(a+c)2(9a2+ 21ac + 8c2) +p√2a √a+ 2cUn−1−|i−j|(p) + U|i−j|−1(p) (Tn(p)−1) ; GS(xj, vxixi+1 ) = p2(a+ 2c)c 8an(a+c)2(−11a2−33ac −16c2)with xn+1 =x1. And finally when only new vertices are taken into account GS(vx0xi, vx0xj) = −a(7a+ 11c) 4n(a+c)2+a 2cUn−1−|i−j|(p) + U|i−j|−1(p) (Tn(p)−1) +εvx0xi(vx0xj), i, j = 1, . . . , n; GS(vx0xi, vxjxj+1 ) = −√ac(11a2+ 23ac + 8c2) 4an(a+c)2 +√ac 2cUn−1−|i−j|(p) + Un−1−|i−j−1|(p) Tn(p)−1 +√ac 2cU|i−j|−1(p) + U|i−j−1|−1(p) Tn(p)−1, GS(vxixi+1 , vxjxj+1 ) = −c(15a2+ 35ac + 16c2) 4an(a+c)2 + (1 + p)Un−1−|i−j|(p) + U|i−j|−1(p) Tn(p)−1+εxi(xj), with i, j = 1, . . . , n in every case and, as usual with xn+1 =x1when required. Applying Proposition 5.6.6 we can obtain the effective resistances for the subdivision network of the n–Wheel. In what follows we compute just some of them as examples. RS(xi, xj) = R(xi, xj), i, j = 0, ..., n i 6=j; RS(x0, vx0xi) = 1 4a+n(a+c) c Un−1(p) Tn(p)−1, i = 1, . . . , n; RS(xj, vx0xi) = 1 4a+5 4 n(a+c) c Un−1(p) Tn(p)−1 +n(a+c) c Un−1−|i−j|(p) + U|i−j|−1(p) Tn(p)−1, i, j = 1, . . . , n; 6.4. Subdivision on Wheel networks for the Laplacian 101 RS(vxixi+1 , xj) = 1 2c+n(a+c) c Un−1(p) Tn(p)−1−n(a+c) cUn−2(p)+1 Tn(p)−1 +n(a+c) cUn−1−|i−j|(p) + U|i−j|−1(p) Tn(p)−1 +n(a+c) cUn−1(p) + Un−1−|i+1−j|(p) + U|i+1−j|−1(p) Tn(p)−1, with i, j = 1, . . . , n and assuming xn+1 =x1once more. In addition, the Kirchhoff index for the subdivision network of the n–Wheel is kS(WS n) = n+ 4np Un−1(p) (Tn(p)−1) −5a2+ 17ac + 16c2 2a(a+c). 6.4 Subdivision on Wheel networks for the Laplacian We consider the wheel network with constant conductances and a subdivision of it for the combinatorial Laplacian. The result of this section can be found in [25]. Let Wnbe the wheel network with vertex set V={x0, x1, . . . , xn}, where x0has degree n, and conductances c(x0, xi) = a > 0for any i= 1, . . . , n,c=c(xi, xi+1) if i= 1, . . . , n −1and c=c(xn, x1), as can be seen in Figure 6.4. For the sake of simplicity we consider that xn+1 =x1. It is known, see for instance [23], that the Green function of Wnis G(x0, x0) = n a(n+ 1)2, G(x0, xi) = −1 a(n+ 1)2, i = 1, . . . , n, G(xi, xj) = −n+ 2 a(n+ 1)2+Un−1−|i−j|(p) + U|i−j|−1(p) 2cTn(p)−1, i, j = 1, . . . , n, where p= 1 + a 2cand U`(x), T`(x)are the Chebyshev polynomials of 1st and 2nd order defined by the recurrence Pm(x) = 2xPm−1(x)−Pm−2(x)m≥0provided that U0(x)=1, U1(x) = xand T−2(x) = −1, T−1(x)=0,respectively. Let us now define the standard subdivision of the wheel network. The new vertices are yi=vx0xiand zi=vxixi+1 if i= 1, . . . , n. The conductances for the new edges are 2a=c(x0, yi)and 2c=c(xi, zi)for i= 1, . . . , n. Whereas, the conductance of the remaining edges follows taking into account relation (4.1). Observe that k(yi)=4aand k(zi)=4cfor i= 1, . . . , n. Moreover, α(x, y) = 1 2,for every pair of adjacent vertices and πS(x0) = n 2and πS(xi) = 3 2, i = 1, . . . , n. Then, the expression of the Green kernel for the subdivision network is given next. Proposition 6.4.1. Let WS nbe the subdivision network of Wn, and for any i, j = 1, . . . , n consider gij(p) = Un−1−|i−j|(p) + U|i−j|−1(p) 2cTn(p)−1. 102 Chapter 6. Stars, Wheels x1 x2 x0 xn z1 z2 zn y1 y2 yn 2a 2a 2c 2c Figure 6.4 Subdivision network of a wheel of n+ 1 vertices Then, the Green kernel for WS nis given by GS(x0, x0) = n(a+ 26c) 4ac(3n+ 1)2, GS(x0, xi) = 1 4ac(3n+ 1) n(a+ 26c) 3n+ 1 −10c, GS(x0, yi) = 1 4ac(3n+ 1)n(a+ 26c) 3n+ 1 −6c, GS(x0, zi) = 1 4ac(3n+ 1)n(a+ 26c) 3n+ 1 −(a+ 10c), GS(xi, xj) = gij (p) + n(a−34c)−20c 4ac(3n+ 1)2, GS(xi, yj) = 1 2gij(p) + n(a−34c)−20c 4ac(3n+ 1)2+1 a(3n+ 1), GS(xi, zj) = 1 2gij(p) + gi j+1(p)+n(a−34c)−20c 4ac(3n+ 1)2−1 4c(3n+ 1), GS(yi, yj) = 1 4gij(p) + εyi(yj) 4a+n(a−34c)−20c 4ac(3n+ 1)2+2 a(3n+ 1), GS(yi, zj) = 1 4gij(p) + gi j+1(p)+n(a−34c)−20c 4ac(3n+ 1)2−a−4c 4ac(3n+ 1), GS(zi, zj) = p+ 1 2gij(p) + n(a−34c)−20c 4ac(3n+ 1)2−1 2c(3n+ 1) +εzi(zj) 4c. Proof. The expressions given in the proposition follow from the expression for the Green kernel obtained in Proposition 4.3.3. We compute one of the cases in order to illustrate the methodology. 6.4. Subdivision on Wheel networks for the Laplacian 103 Firstly, we compute the constant β=1 (n+m)2P s,r∈V G(s, r)πS(r)πS(s) + 1 (n+m)2P r∼s 1 k(vrs) =n 4a(3n+ 1)2"n−3 n+ 12 +a c+ 1#, where we have taken into account that P r∈V G(s, r)=0and hence X r∈V G(s, r)πS(r) = n−3 2G(s, x0). Consider zi=vxixi+1 and zj=vxjxj+1 ,then GS(zi, zj) = 1 4G(xi, xj) + G(xi+1, xj) + G(xi, xj+1) + G(xi+1, xj+1) −1 2(3n+1) n P `=0G(xj, x`) + G(xj+1, x`) + G(xj, x`) + G(xj+1, x`)πS(x`) +εzj(zi) k(zi)−1 (3n+ 1)k(zi)−1 (3n+ 1)k(zj)+β =−n+ 2 a(n+ 1)2+2U|i−j|−1(p) + U|i+1−j|−1(p) + U|i−j−1|−1(p) 8cTn(p)−1 +2Un−1−|i−j|(p) + Un−1−|i+1−j|(p) + Un−1−|i−j−1|(p) 8cTn(p)−1 +n−3 (3n+ 1)(n+ 1)2+εzj(zi) 4c−2 (3n+ 1)4c+β = (a+ 4c)Un−1−|i−j|(p) + U|i−j|−1(p) 8c2Tn(p)−1−n(5a+ 34c)+2a+ 20c 4ac(3n+ 1)2 +εzi(zj) 4c. To end up the section we compute the Kirchhoff index of the standard subdivision graph associated with the wheel Wn. Corollary 6.4.2. The Kirchhoff index of the standard subdivision network of WS n is kS(WS n) = 3n2(a+c)−25cn 4ac +n(3n+ 1)7Un−1(p)+2Un−2(p)+2 8cTn(p)−1. 110 Chapter 7. Future Work the correspondent expression of the Green kernel and, after some calculation to get resistance distances involved in the cited expression obtaining a beautiful result GF q(xi, xj) ω(xi)ω(xj)=R(x1, xmin{i,j})R(x1, xmax{i,j}) R(x1, xn) for every i, j = 1, . . . , n. 7.2 Path–subdivision In this second work we have two targets to be achieved: from a first point of view we complete our study of the so called electrical subdivision of a network by considering a generalization that models the most general case that has sense, or it is applicable, for facing diffusion problems. But, and from another point of view, as we consider the case of non-singular Schrödinger operators, we get a contribution to the computation of generalized inverse matrices of large non singular positive semi– definite M–matrices from given generalized inverse matrices of smaller dimension and obviously related to the previous ones. In these second work, from a technical point of view, we also change of paradigm as we obtain the solutions of boundary value problem that do include Dirichlet boundary value problems as well. Thus a different situation, more ellaborated and that imposes a longer algorithm has to be treated. 7.2.1 Electrically compatible path–partial subdivision Graphs and networks can be modified in order to obtain other graphs or networks. Vertices and/or edges can be removed or added in an extremely vaste variety of ways in order to obtain new discrete structures that are related with the former ones. Correspondingly the conductance function may be modified too. There are so many operations that transform a given discrete structure into others, simpler or much more complicated. Up to now we have extensively treated an electrically compatible subdivision procedure of all the edges of a given discrete structure and also a somehow partial– generalization of it, that can be understood in both senses; as it do not forces all edges to be subdivided thus allowing some degrees of freedom it should be clearly considered a generalization, but also it consists in a particular case of the idea, being applied to just one edge or to a few of them, so using not the hole transformation. By the time of baptism we had many doubts and quite a few controversial. But a really significative generalization of the initial idea came to our minds sometime: using subdivision of just a precise subset of the initially given edge set of the discrete structure but allowing the possibility of every edge to be subdivided in a different way, in the sense of being substituted by a path of different length. For sure we are still installed in the electric circuit setting (by now it is clear that this framework is clearly overcame) but we again force the substituting path to be equivalent to the former edge. Specifically what we discussed to name generalized electrical subdivision of networks but finally propose to be called electrical compatible path–partial subdivision of 7.2. Path–subdivision 111 networks, consists in, given a network Γ=(V, E, c)replacing only some former edges {x, y} ∈ Eby a path Pxy ={x=v0 xy ∼v1 xy ∼ ··· ∼ v`xy xy ∼v`xy+1 xy =y}, not just of length two, but of length `xy + 1 instead, and the conductance function to be defined on the new vertices introduced in this way such that the electrical condition of a generalized series connection is fulfilled. x y z v1 xy v2 xy v3 xy Thus a brand new ΓpS = (VpS , EpS, cpS )is defined as follows. Given a two sets partition of the former edge set E, say E1, E2⊂Esuch that E=E1∪E2and E1∩ E2=∅,suppose that the edges in E1are those to be electrically path–subdivided while the edges corresponding to E2are those devoted to stay. Then the new vertex set VpS is the former set Vto which the new vertices included in the collection of paths has been added. Hence some new v1 xy, v2 xy, . . . , v`xy xy vertices are defined for every single former edge {x, y} ∈ E1to be erased. Thus, being `xy the number of new vertices in a substituting path, easily |VpS |=|V|+X {x,y}∈E1 `xy.The new edges set EpS is composed by the initially given edges on Γnot to be replaced, that is E2⊂Eand the set of new edges that are defined in the paths that substitute the former edges in E1. In this way it turns out that |EpS |=|E2|+X {x,y}∈E1 (`xy + 1) = |E|+X {x,y}∈E1 `xy.Finally the conductance function cpS :VpS ×VpS →[0,+∞)is defined almost freely on the new created edges (vi xy, vi+1 xy )for i= 0, . . . , `xy for every Pxy adjoined path. We will denote them as cxy(vi xy, vi+1 xy )as though there is no possible confusion with former existing conductances and accept an absolutely arbitrary choice of values if that fulfills the electrically compatible series connection condition, which is (for a non–singular Schödinger type operator) 1 ω(x)c(x, y)ω(y)=1 ω(x)cxy(x, v1 xy)ω(v1 xy)+···+1 ω(v`xy−1 xy )cxy(v`xy −1 xy , y)ω(y) (7.3) 112 Chapter 7. Future Work and is not altered whenever {x, y} ∈ E2. Remark: we would like to point out that this quite bizarre notation cannot be simplified for our purposes. Even though, the names we have chosen for the vertices avoid any kind of confusion so, in the sequel, we are not using cpS anymore in an obvious abuse of notation. Moreover, as ΓpS is clearly non directed (as a graph) we must take into account that for every {x, y} ∈ E1paths Pxy and Pyx consists in the same vertex and edges sets, thus we write Pxy =Pyx.Also `xy =`yx and vi xy =v`yx+1−i yx for i= 1, . . . , `xy.Also we consider x=v0 xy =v`yx+1 yx and y=v0 yx =v`xy+1 xy in a certain abuse of notation. Also it is very important for us to notice that this definition of the electrical subdivision of a network has a very clear physical inspiration and sense as it models substitution of a wire in an electric circuit by equivalent more complicated branches. And allows the possibility of replacing only some of the components of an initial given electric circuit. Also we want to point out that physically, we are simulating putting rheostats in any point of the wire. This is a crucial difference with respect to the standard graph subdivision that can be found in the literature because it obliges to consider two substituting wires that are equal and this new electrical subdivision allows substitutions that are globally equivalent but with no other restriction, in particular new wires can behave differently one from each others. The definition of cxy cannot be misunderstood as all the edges in Exy have both vertices in Vxy.Hence, by the sake of simplicity, it will be denoted as c. Moreover for each subdivided edge, there exist infinitely many different choices of conductances fulfilling (4.1), so that different choices will lead to different subdivision networks. With this definition of the modified structure then, If LS qωdenotes the positive semi–definite Schrödinger operator related to the weight ω∈ C(VS)of ΓS,then for any u∈ C(VS)we have that the so called Doob transform expression of LS qωis LS qω(u)(x) = X {x,y}∈E1 c(x, v1 xy)ω(v1 xy) u(x) ω(x)−u(v1 xy) ω(v1 xy)! +X {x,y}∈E2 c(x, y)ω(y)u(x) ω(x)−u(y) ω(y), when x∈V(is an old vertex of the former network), whereas LS qω(u)(vi xy) = c(vi−1 xy , vi xy)ω(vi−1 xy ) u(vi xy) ω(vi xy)−u(vi−1 xy ) ω(vi−1 xy )! +c(vi xy, vi+1 xy )ω(vi+1 xy ) u(vi xy) ω(vi xy)−u(vi+1 xy ) ω(vi+1 xy )! when vi xy, i = 1, . . . , `xy is a new inserted vertex of some of the attached paths. 7.2.2 Overall approach Our goal is, given f∈ C(VsP ),to obtain a solution of LS qω(u) = f, on VsP (7.4) 7.2. Path–subdivision 113 that is u∈ C(VsP )with the help of the solution of two other auxiliary problems: a Dirichlet boundary value problem on every attached path, and a conveniently stated Poisson problem defined on the base network Γ,that is on former V. On every Pxy inserted we will pose a Dirichlet boundary value problem. As these problems are always compatible, their solution will establish de values of the overall solution uon the new inserted vertices vi xy for i= 1, . . . , `xy and every {x, y} ∈ E1. These values will be defined explicitly depending on the unknown values u(x)and u(y)(the ends of each path, vertices of the former network) for every path Pxy. Once all the battery of Dirichlet boundary value problems will be solved, a rather well known technique of contracting the data, solving a Poisson problem on Γfor this contracted data and finally extension of the accomplished solution to ΓSthat we have used in all our previous works will lead to a solution of the initial problem. Finally, after obtaining the solution of (7.4) we will be ready for obtaining the correspondent Green’s function. 7.2.3 Dirichlet boundary value problems Now we recover from Subsection 3.5.1 what a Dirichlet boundary value problem is and we explain some inquiries of the way we solve this situation. Generally speaking a Dirichlet problem consists in, given a proper connected subset W(V, f ∈ C(W)and g∈ C(W),finding u∈ C(W)such that Lqω(u) = fon W; u=gon ∂W. (7.5) Such a boundary value problem has a unique solution (see [7]) for any data f∈ C(W)and g∈ C(∂W)that can be found equivalently by solving Lqω(v) = f−Lqω(g)on W; v= 0 on ∂W, (7.6) as u=v+gon Weasily, once using that a function is extended by zero outside the domain where it is canonically defined. 7.2.4 The Green’s function of a path We apply the previous general setting when W=◦ Pxy (hence ∂Pxy ={x, y}) for every {x, y} ∈ E1.Thus there will be some Dirichlet boundary value problems to be solved, just a few or quite a lot of them depending on |E1|.Remarkably all the solutions of these problems do not share support, or, better expressed, for every vertex vi xy the obtained value u(vi xy)follows from one specific Dirichlet problem, hence it is well defined. Specifically for every {x, y} ∈ E1substituted by Pxy we write LS qω=LPxy qωthe boundary Dirichlet value problem on Pxy (VSis established as LPxy qω(u)(vi xy) = f(vi xy)i= 1, . . . , `xy u(v0 xy) = u(x) u(v`xy+1 xy ) = u(y) 114 Chapter 7. Future Work where u(x)and u(y)are the values that u∈ C(VsP )the required solution from (7.4) will take. By now there are presumed and treated as known data. This required u∈ C(Pxy)can be obtained, after (7.6) and some calculation, by solving LPxy qω(v) = f+u(x)c(x, v1 xy)εv1 xy +u(y)c(v`xy xy , y)εv`xy xy on ◦ Pxy v= 0 on {x, y}=∂Pxy (7.7) and then u=v+u(x)εx+u(y)εy by using Green’s operator and Green’s function obtained from the first on progress work that we have just exposed in the previous subsection. As we have just said, this solution of a Dirichlet problem can be considered for every edge {x, y} ∈ E1that has been replaced by a path in ΓS.Then we denote all these functions as uxy and remark that they attain their corresponding values within the paths, while coinciding with u, a function defined on Vat the boundary of the paths, that is, at xand y. At this point we are set to obtain the expression of the Green’s function for a path in the case of a Schrödinger type operator, a result by itself that worths a publication as we have mention previously 7.2.5 Related Poisson problem on V The aim of this section is to obtain a solution of the Poisson problem in ΓSin terms of the solution of an appropriate Poisson problem on Γ.So we now apply our familiar procedure of contracting data to V, solving a convenient Poisson problem on Γand finally extending its solution to VsP as this extension is the function we were looking for from the very beginning. Once the auxiliary Dirichlet problems over the different attached paths have been solved, we use their solutions to define a Poisson problem on the basis network Γ The start of this last stage begins with defining, for each h∈ C(VsP )the contraction of hto V, h ∈ C(V),as h(x) = h(x) + X {x,y}∈E1 c(x, v1 xy)(GPxy qω)(v1 xy), x ∈V, (7.8) hence establishing the appropriate Poisson problem LS qω(u)(x) = f(x) for x∈Vand f∈ C(VsP )from the initial given problem 7.4. This expression turns to be a Poisson problem for a Schrödinger type operator is some compatibility conditions are fulfilled. After a little calculation the resulting conditions to be imposed for conductances and weights can be written such that 1 c(x, y)=1 c(x, v1 xy) 1 GPxy qω(v1 xy, v`xy xy ) 1 c(v`xy xy , y)(7.9) 7.3. Some other ideas 115 So, with the help of the Green’s function for the previous Schrödinger operator we obtain u∈ C(V)that finally is extended to the desired solution of (7.4) by using the extension of uto VSwith respect to f,uf∈ C(VsP ),that is defined as uf(x) = u(x); uf(vi xy) = GPxy qωf(vi xy) + c(x, v1 xy)GPxy qω(vi xy, v1 xy)u(x) +c(v`xy xy , y)GPxy qω(vi xy, v`xy xy )u(y) (7.10) for all x∈V, i = 1, . . . , `xy and every {x, y} ∈ F. And once the boundary value problem is solved, the computation of the corresponding Green’s function follows. 7.3 Some other ideas To end this chapter we introduce a few ideas that have come to our mind sometime. They are not only attractive as they represent a more or less natural way of developing our research task from our current point, but they are also in agreement with the interests of the research group Mapthe, to which I belong. 1. λ > 0 The very first idea, in order to continue with our present research, probably should be attempting the solution of the case of a positive definite Schrödinger operator in a generalized subdivision network. This is a natural prolongation of our works and we are now initiated in the use of host networks. Embedding a given network into a suitable host network should probably be definitive for us in order to extend our result to the case where λ > 0. This technique, see [39, 40] is commonly used in the context of electrical networks and Markov chains. Provided Lqa positive definite Schrödinger operator on Γ,that is q=qω+λfor some ω∈Ω(Γ) and λ > 0,we can consider a new network constructed by adding to Γa brand new vertex, that will represent an absorbing state, that is joined with every each vertex in Γ through edges whose conductances are the, so called, diagonal excess after the use of the Doob transform. After [9], given λ > 0, ω ∈Ω(V)and ˆx /∈V, we should consider the network Γλ,ω = (V∪{ˆx}, cλ,ω)with cλ,ω(x, y) = c(x, y)for x, y ∈Vbut cλ,ω(x, ˆx) = λω(x)for all x∈V. If we denote the combinatorial Laplacian for the new network Γλ,ω as Lλ,ω and define a weight function on the new network, ˆω∈Ω(V∪ˆx),such that ˆω(ˆx) = √2 2and ˆω(x) = √2 2ω(x)for the rest vertices x∈V, it turns out that there exists a simple relation between the positive definite Schrödinger operator Lqon Γand a new positive semi– definite Schrödinger operator on Γλ,ω . Lλ,ω ˆq(u) = Lq(u|V)−λωu(ˆx)on V. that will permit us to extend our results as we mentioned earlier. 116 Chapter 7. Future Work 2. Puncturing a net between non adjacent vertices. In all the works we have intended, in relation with networks and their subdivision procedures, we have always considered the substitution of edges by, eventually an arbitrary length path so that the remaining discrete structure is electrically equivalent to the given initial one. But we have never tried a puncture of the network between two non–adjacent vertices. As our closed expressions for the Green’s function that we have found do not need adjacency as a necessary condition, we think there probably might be a way of joining paths (or much more elaborated networks) to a given network so as to keep electrical equivalence. 3. Spectral study of Schrödinger operators. Some members of our research group have occasionally devoted their attention punctually to the so called Kron–reduction operation on networks. The Kron reduction process is ubiquitous in classic circuit theory and in other related theories such as electrical impedance tomography, smart grid monitoring, analysis and simulation of induction motors, for example. The Kron reduction process in used to obtain lower dimensional electrically–equivalent networks. We (the research group) strongly believe that we have the tools to encompass the problem of studying the spectrum of Schrödinger type operators in this situation, so this could be one line of research in which we could collaborate, if the group take this direction. 4. Probabilistic interpretation for Schödinger operators Finally another alternative of developing our work in the very soon future to come is concerned with the fact that some of the concepts above mentioned, have a well–known probabilistic counterpart. For instance the effective resistance is related with the escape probability for a reversible Markov chain. Therefore, the effective resistance with respect to a non–negative value and a weight will correspond to a generalization of the escape probability. In turns, the equilibrium measure with respect to λand ωcan be seen as a generalization of the hitting time. As a by–product of the expression for the effective resistance with respect to a non–negative value and a weight, Bendito et al. obtained in [10] a full generalization of Foster’s formulae; see [8, 57, 69, 72] for the standard case. To get the formulae they introduce a generalization of the transition probability matrix that takes into account the probability of transitioning from one state to another in a single step or remaining in the same state. The probability laws governing the evolution of the chain are given by the (one step)transition probability kernel with respect to λand ω,Pλ,ω ∈ C(V× V), that is defined for any x, y ∈Vas Pλ,ω(x, y) = c(x, y) + λ ω(x)ω(y)ω(y) k(x) + q(x)ω(x) .(7.11) As we can see, the main novelty in our definition is the consideration of a non– negative probability of remaining at vertex xgiven by the term λω2(x) k(x) + q(x). 7.3. Some other ideas 117 The future work we will try to develop should consist in interpreting all the results obtained for Schrödinger operators in probabilistic terms. For instance, we can expect for a formula for the mean first passage times for generalized Markov chains in terms of the group inverse of the corresponding Schrödinger operator; see [56]. This is also related with the inverse M–matrix problem. 8 Conclusions In this last chapter we would like to include some brief conclusions and remarks that we have reached and find interesting to expose, after devoting our efforts to the work we have explained so far. 1. On discrete potential theory The first point we would like to highlight is the framework within we have developed our research. What we call discrete potential theory is not only a set of technicalities that mimick potential theory from the continuum, and that are perfectly constructed. We conceived functions, linear operators, inverse operators, . . . in intimately connection with the network where they are applied. Of course we obtain a gain with the non–coordinate notation that we use, treating all vertices as they are the same, at the same time that we see them different one from the others. But the main characteristic of the way we work, is a kind of a play with the structure. Because we apply changes on it, we modify it, sometimes annexing vertices, sometimes erasing edges,. . . In this way it becomes a very succesful manner to obtain our desired results in the solution of discrete boundary value problems. Moreover we have the feeling now that we have to have friends we have never heard of them. And we say this because we have recently discovered, [42, 62], that the notation and vocabulary that we use also appears in publications devoted to topics that are quite far away from our scope, at least apparently. Social networks, pattern recognition, digital image processing, machine learning are worlds where discrete potential theory also applies. Without any doubt this is not a coincidence. We give to this fact a very positive interpretation, of course. 2. On electrical subdivision Surprisingly we found very little work devoted to the subdivision of a graph procedure and an electric circuit implemention of it, even though the obvious relationship. We know understand what at that moment we valued as simply incredible. The topic for sure deserved attention, but graphs are not capable to face it. A more developed structure had to be used. And fortunately we were in touch with a tool likely to be used to adress the situation. From an electric circuit point of view, when a series connection is considered an equivalent 126 Bibliography [48] R.M. Foster. The average impedance of an electrical network. Contributions to Applied Mechanics (Reissner Anniversary Volume), Ann Arbor, Edwards Brothers, Inc., 333–340, 1949. [49] X. Gao, Y. Luo and W. Liu. Kirchhoff index in line, subdivision and total graphs of a regular graph. Discrete Appl. Math.,160: 560–565, 2012. [50] X. Ghosh, S. Boyd and A. Saberi. Minimizing effective resistances of a graph. SIAM Review,50: 37–66, 2008. [51] I. Gutman and B. Mohar. The quasi–Wiener and the Kirchhoff indices coincide. J. Chem. Inf. Comput. Sci,36: 982–985, 1996. [52] I. Gutman and W. Xiao. Generalized inverse of the Laplacian matrix and some applications. Bull. CXXIX de l’Académie serbe des sciences et des arts, 29: 15–23, 2004. [53] S. Huang, J. Zhou and C. Bu. Some results on Kirchhoff index and degree– Kirchhoff index. MATCH Comm. Math. Comput. Chem.,75: 207–222, 2016. [54] J. J. Hunter. The Role of Kemeny’s Constant in Properties of Markov Chains. Comm. Stat. Theo. Meth.,43 (7), 1309–1321, 2014. [55] M. Kac. Can one hear the shape of a drum? Am. Math. Mon.,73: 1–23, 1966. [56] S.J. Kirkland and M. Neumann. Group inverses of M–matrices and their applications. Chapman & Hall/CRC Applied Mathematics and Nonlinear Science Series. CRC Press, Boca Raton, FL, 2013. ISBN 978-1-4398-8858-2. [57] D.J. Klein. Resistance distance sum rules. Croat. Chem. Acta,75: 633–649, 2002. [58] D. J. Klein and M. Randić. Resistance distance. J. Math. Chem.,12: 81–95, 1993. [59] L.H. Lim. Hodge Laplacians on graphs. SIAM Rev.,62: 685–715, 2020. [60] J. B. Liu and J. Cao. The resistance distances of electrical networks based on Laplacian generalized inverse. Neurocomputing,167: 306–310, 2015. [61] X. Liu, J. Zhou and C. Bu. Resistance distance and Kirchhoff index of R- vertex join and R-edge join of two graphs. Discret. Appl. Math.,187: 130–139, 2015. [62] F. Lozes, A. Elmoataz, and O. Lezoray, Partial Difference Operators on Weighted Graphs for Image Processing on Surfaces and Point Clouds IEEE Trans. Im. Proc.,23 (9): 3896–3909, 2014 [63] I. Lukovits, S. Nikolić and N. Trinajstić. Resistance distance in regular graphs. Int. J. Quant. Chem,71: 217–225, 1999. [64] R. Merris. Laplacian Matrices of Graph: A Survey. Linear Algebra Appl., 197: 143–176, 1994. [65] B. Mohar. The Laplacian spectrum of graphs. Graph Theory, combinatorics, and applications, Wiley-Intersci. Publ., Wiley, New York, vol 2: 871–898, 1991. Bibliography 127 [66] J.J. Molitierno. Applications of Combinatorial Matrix Theory to Laplacian Matrices of Graphs. Discrete Mathematics and Its Applications (Boca Raton). CRC Press, Boca Raton, FL, 2012. ISBN1978-1-4398-6337-4. [67] M.E.J. Newman. Networks: An Introduction. Oxford University Press, Oxford, 2010. ISBN 978-0-19-920665-0. [68] J.L. Palacios. Closed–form formulas for Kirchhoff index. Int. J. Quant. Chem,81: 135–140, 2001. [69] J.L. Palacios. Foster’s formulas via probability and the Kirchhoff index. Methodol. Comput. Appl. Probab.,6: 381–387, 2004. [70] K. Stephenson, and M. Zelen. Rethinking Centrality: Methods and Examples. Soc. Netw.,11: 1–37, 1989. [71] L. Sun, W. Wang, J. Zhou and C. Bu. Some results on resistance distances and resistance matrices. Linear Multilinear Algebra,63: 523–533, 2015. [72] P.Tetali. Random walks and the effective resistance of networks. J. Theoret. Probab., 4: 101–109, 1991. [73] H. Wiener. Structural Determination of Paraffin Boiling Points. J. Amer. Chem. Soc.,69: 17–20, 1947. [74] W. Xiao and I. Gutman. Resistance distance and Laplacian spectrum. Theor. Chem. Acc.,110: 284–289, 2003. [75] P. Xie, Z. Zhang and F. Comellas. The normalized Laplacian spectrum of subdivisions of a graph. Appl. Math. and Comp,286: 250–256, 2016. [76] Y. Yang. The Kirchhoff index of subdivisions of graphs. Discrete Appl. Math., 171: 153–157, 2014. [77] Y. Yang and D.J. Klein. A recursion formula for resistance distances and its applications. Discrete Appl. Math.,161: 2702–2715, 2013. [78] H.P. Zhang, Y.J. Yang and C.W. Li. Kirchhoff index of composite graphs. Discrete Appl. Math.,157: 2918–2927, 2009. [79] H.Y. Zhu, D.J. Klein and I. Lukovits. Extension of the Wiener number. J. Chem. Inf. Comput. Sci,36: 420–428, 1996.