Dynamical systems associated with adjacency matrices

Delio Mugnolo

doi:10.3934/dcdsb.2018190

Article Contents

2018, Volume 23, Issue 5: 1945-1973. Doi: 10.3934/dcdsb.2018190

This issue Previous Article Explosive synchronization in mono and multilayer networks Next Article Evolving multiplayer networks: Modelling the evolution of cooperation in a mobile population

Dynamical systems associated with adjacency matrices

Delio Mugnolo

Delio Mugnolo, Lehrgebiet Analysis, Fakultät Mathematik und Informatik, FernUniversität in Hagen, D-58084 Hagen, Germany

Received: January 31, 2017

Revised: August 31, 2017

Early access: May 2018

Published: May 2018

The author was supported by the Center for Interdisciplinary Research (ZiF) in Bielefeld, Germany, within the framework of the cooperation group on "Discrete and continuous models in the theory of networks".

Abstract Full Text(HTML) Figure(2) Related Papers Cited by

Abstract

We develop the theory of linear evolution equations associated with the adjacency matrix of a graph, focusing in particular on infinite graphs of two kinds: uniformly locally finite graphs as well as locally finite line graphs. We discuss in detail qualitative properties of solutions to these problems by quadratic form methods. We distinguish between backward and forward evolution equations: the latter have typical features of diffusive processes, but cannot be well-posed on graphs with unbounded degree. On the contrary, well-posedness of backward equations is a typical feature of line graphs. We suggest how to detect even cycles and/or couples of odd cycles on graphs by studying backward equations for the adjacency matrix on their line graph.

Keywords:

Mathematics Subject Classification: 47D06, 05C50, 39A12.

Citation:

Full Text(HTML)

Figure 2.1. The graph H and its line graph G in Example 2.11.1); here ${\rm{v}}_i\simeq {\rm{e}}_i$

Download: Full-size image PowerPoint slide

Figure 2.2. The graph H and its line graph G in Example 2.11.2); again, ${\rm{v}}_i\simeq {\rm{e}}_i$

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	H. Baloudi, S. Golénia and A. Jeribi. The adjacency matrix and the discrete Laplacian acting on forms, arXiv: 1505.06109 2015.
[2]	J. von Below, An index theory for uniformly locally finite graphs, Lin. Algebra Appl., 431 (2009), 1-19. doi: 10.1016/j.laa.2008.10.030.
[3]	A. Bobrowski, From diffusions on graphs to Markov chains via asymptotic state lumping, Ann. Henri Poincaré A, 13 (2012), 1501-1510. doi: 10.1007/s00023-012-0158-z.
[4]	M. Bonnefont, S. Golénia and M. Keller. Eigenvalue asymptotics for schrödinger operators on sparse graphs, Eigenvalue asymptotics for schrödinger operators on sparse graphs, Ann. Inst. Fourier, 65 (2015), 1969-1998. doi: 10.5802/aif.2979.
[5]	A. E. Brouwer and W. H. Haemers. Spectra of Graphs Universitext. Springer-Verlag, Berlin, 2012. doi: 10.1007/978-1-4614-1939-6.
[6]	S. Cardanobile, The $L^2$ -strong maximum principle on arbitrary countable networks, Lin. Algebra Appl., 435 (2011), 1315-1325. doi: 10.1016/j.laa.2011.03.001.
[7]	D. M. Cardoso, D. Cvetković, P. Rowlinson and S. K. Simić, A sharp lower bound for the least eigenvalue of the signless Laplacian of a non-bipartite graph, Lin. Algebra Appl., 429 (2008), 2770-2780. doi: 10.1016/j.laa.2008.05.017.
[8]	D. Cartwright and W. Woess, The spectrum of the averaging operator on a network (metric graph), Illinois J. Math., 51 (2007), 805-830.
[9]	D. Chakrabarti, Y. Wang, C. Wang, J. Leskovec and C. Faloutsos, Epidemic thresholds in real networks, ACM Transactions on Information and System Security (TISSEC), 10 (2008), 1-26. doi: 10.1145/1284680.1284681.
[10]	R. Chill and E. Fašangová, Gradient Systems MatFyzPress, Prague, 2010.
[11]	F. Chung and S.-T. Yau, Coverings, heat kernels and spanning trees, Electron. J. Combin. , 6 (1998), Research Paper 12, 21 pp.
[12]	F. Chung, The heat kernel as the pagerank of a graph, Proc. Natl. Acad. Sci. USA, 104 (2007), 19735-19740. doi: 10.1073/pnas.0708838104.
[13]	Ó. Ciaurri, T. A. Gillespie, L. Roncal, J. L. Torrea and J. L. Varona, Harmonic analysis associated with a discrete Laplacian, J. Anal. Math., 132 (2017), 109-131. doi: 10.1007/s11854-017-0015-6.
[14]	L. Collatz and U. Sinogowitz, Spektren endlicher grafen, Abh. Math. Seminar Univ. Hamburg, 21 (1957), 63-77. doi: 10.1007/BF02941924.
[15]	D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs – Theory and Applications, Pure Appl. Math. Academic Press, New York-London, 1980.
[16]	D. Cvetković, P. Rowlinson and S. Simić, Spectral Generalizations of Line Graphs: On Graphs With Least Eigenvalue -2, volume 314. Cambridge University Press, Cambridge, 2004. doi: 10.1017/CBO9780511751752.
[17]	D. Cvetković, P. Rowlinson and S. Simić, An Introduction to the Theory of Graph Spectra, volume 75 of London Math. Soc. Lect. Student Texts. Cambridge Univ. Press, 2010.
[18]	D. Cvetković and S. K. Simić, Towards a spectral theory of graphs based on the signless Laplacian, Ⅰ, Publ. Inst. Math.(Beograd), 85 (2009), 19-33. doi: 10.2298/PIM0999019C.
[19]	E. B. Davies, Spectral Theory and Differential Operators, volume 42 of Cambridge Studies Adv. Math., Cambridge Univ. Press, Cambridge, 1995. doi: 10.1017/CBO9780511623721.
[20]	E. B. Davies, Linear Operators and Their Spectra, Cambridge Univ. Press, Cambridge, 2007. doi: 10.1017/CBO9780511618864.
[21]	L. S. de Lima, C. S. Oliveira, N. M. M. de Abreu and V. Nikiforov, The smallest eigenvalue of the signless Laplacian, Lin. Algebra Appl., 435 (2011), 2570-2584. doi: 10.1016/j.laa.2011.03.059.
[22]	R. Diestel, Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 2005.
[23]	M. Doob, An interrelation between line graphs, eigenvalues, and matroids, J. Comb. Theory. Ser. B, 15 (1973), 40-50. doi: 10.1016/0095-8956(73)90030-0.
[24]	Z. Dvořák and B. Mohar, Spectral radius of finite and infinite planar graphs and of graphs of bounded genus, J. Comb. Theory. Ser. B, 100 (2010), 729-739. doi: 10.1016/j.jctb.2010.07.006.
[25]	K.-J. Engel and R. Nagel, One-Parameter Semigroups for Linear Evolution Equations, volume 194 of Graduate Texts in Mathematics, Springer-Verlag, New York, 2000.
[26]	E. Estrada, E. Hameed, N. Hatano and M. Langer, Path Laplacian operators and superdiffusive processes on graphs - I -one dimensional case, Lin. Algebra Appl., 523 (2017), 307-334. doi: 10.1016/j.laa.2017.02.027.
[27]	S. Evdokimov, M. Karpinski and I. Ponomarenko, Compact cellular algebras and permutation groups, Disc. Math., 197 (1999), 247-267. doi: 10.1016/S0012-365X(99)90071-7.
[28]	M. Fiedler, Algebraic connectivity of graphs, Czech. Math. J., 23 (1973), 298-305.
[29]	A. Ganesh, L. Massoulié and D. Towsley, The effect of network topology on the spread of epidemics, In INFOCOM 2005, 2 (2005), 1455–1466. doi: 10.1109/INFCOM.2005.1498374.
[30]	J. S. Geronimo, An upper bound on the number of eigenvalues of an infinite dimensional Jacobi matrix, J. Math. Phys., 23 (1982), 917-921. doi: 10.1063/1.525458.
[31]	D. F. Gleich, PageRank beyond the Web, SIAM Review, 57 (2015), 321-363. doi: 10.1137/140976649.
[32]	C. D. Godsil and B. D. McKay, Feasibility conditions for the existence of walk-regular graphs, Lin. Algebra Appl., 30 (1980), 51-61. doi: 10.1016/0024-3795(80)90180-9.
[33]	C. Godsil, State transfer on graphs, Disc. Math., 312 (2012), 129-147. doi: 10.1016/j.disc.2011.06.032.
[34]	C. Godsil and G. Royle. Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 2001. doi: 10.1007/978-1-4613-0163-9.
[35]	S. Golénia, Unboundedness of adjacency matrices of locally finite graphs, Lett. Math. Phys., 93 (2010), 127-140. doi: 10.1007/s11005-010-0390-8.
[36]	M. Haase, Functional Analysis – An Elementary Introduction, Amer. Math. Soc., Providence, RI, 2014.
[37]	S. Haeseler, M. Keller, D. Lenz and R. Wojciechowski, Laplacians on infinite graphs: Dirichlet and Neumann boundary conditions, J. Spectral Theory, 2 (2012), 397-432.
[38]	H. Hanche-Olsen and H. Holden, The Kolmogorov-Riesz compactness theorem, Expos. Mathematicae, 28 (2010), 385-394. doi: 10.1016/j.exmath.2010.03.001.
[39]	F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.
[40]	R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge Univ. Press, Cambridge, 1991. doi: 10.1017/CBO9780511840371.
[41]	T. Kato, On the semi-groups generated by Kolmogoroff's differential equations, J. Math. Soc. Jap., 6 (1954), 1-15. doi: 10.2969/jmsj/00610001.
[42]	M. Keller and D. Lenz, Dirichlet forms and stochastic completeness of graphs and subgraphs, J. Reine Angew. Math., 666 (2012), 189-223. doi: 10.1515/CRELLE.2011.122.
[43]	M. Keller, D. Lenz, H. Vogt and R. Wojciechowski, Note on basic features of large time behaviour of heat kernels, J. Reine Angew. Math., 708 (2015), 73-95. doi: 10.1515/crelle-2013-0070.
[44]	R. Killip and B. Simon, Sum rules for jacobi matrices and their applications to spectral theory, Ann. Math., 158 (2003), 253-321. doi: 10.4007/annals.2003.158.253.
[45]	D. Lenz and K. Pankrashkin, New relations between discrete and continuous transition operators on (metric) graphs, Int. Equations Oper. Theory, 84 (2016), 151-181. doi: 10.1007/s00020-015-2253-2.
[46]	A. Lunardi, Analytic Semigroups and Optimal Regularity in Parabolic Problems, volume 16 of Progress in Nonlinear Differential Equations and their Applications. Birkhäuser, Basel, 1995.
[47]	A. Meyerowitz, Largest adjacency eigenvalue of line graphs, MathOverflow, http://www.mathoverflow.net/q/262340 (version: 2017-02-16).
[48]	B. Mohar, The spectrum of an infinite graph, Lin. Algebra Appl., 48 (1982), 245-256. doi: 10.1016/0024-3795(82)90111-2.
[49]	B. Mohar and W. Woess, A survey on spectra of infinite graphs, Bull. London Math. Soc., 21 (1989), 209-234. doi: 10.1112/blms/21.3.209.
[50]	D. Mugnolo, Gaussian estimates for a heat equation on a network, Networks Het. Media, 2 (2007), 55-79. doi: 10.3934/nhm.2007.2.55.
[51]	D. Mugnolo, A variational approach to strongly damped wave equations, In H. Amann, W. Arendt, M. Hieber, F. Neubrander, S. Nicaise, and J. von Below, editors, Functional Analysis and Evolution Equations – The Günter Lumer Volume, pages 503–514. Birkh¨auser, Basel, 2008. doi: 10.1007/978-3-7643-7794-6_30.
[52]	D. Mugnolo, Parabolic theory of the discrete $p$ -Laplace operator, Nonlinear Anal., Theory Methods Appl., 87 (2013), 33-60. doi: 10.1016/j.na.2013.04.002.
[53]	D. Mugnolo, Semigroup Methods for Evolution Equations on Networks, Underst. Compl. Syst. Springer-Verlag, Berlin, 2014. doi: 10.1007/978-3-319-04621-1.
[54]	V. Müller, On the spectrum of an infinite graph, Lin. Algebra Appl., 93 (1987), 187-189. doi: 10.1016/S0024-3795(87)90324-7.
[55]	R. Nagel, editor. One-Parameter Semigroups of Positive Operators, volume 1184 of Lect. Notes Math. Springer-Verlag, Berlin, 1986.
[56]	E. M. Ouhabaz, Analysis of Heat Equations on Domains, volume 30 of Lond. Math. Soc. Monograph Series. Princeton Univ. Press, Princeton, NJ, 2005.
[57]	S. Sarkar and K. L. Boyer, Quantitative measures of change based on feature organization: Eigenvalues and eigenvectors, In Conference on Computer Vision and Pattern Recognition (CVPR), pages 478–483. IEEE, 1996.
[58]	A. E. Taylor, Introduction to Functional Analysis, Wiley, New York, 1958.
[59]	G. Tinhofer, Graph isomorphism and theorems of Birkhoff type, Computing, 36 (1986), 285-300. doi: 10.1007/BF02240204.
[60]	P. van Mieghem, The $N$ -intertwined SIS epidemic network model, Computing, 93 (2011), 147-169. doi: 10.1007/s00607-011-0155-y.
[61]	P. Van Mieghem, J. Omic and R. Kooij, Virus spread in networks, IEEE/ACM Trans. Networking, 17 (2009), 1-14.
[62]	Y. Wang, D. Chakrabarti, C. Wang and C. Faloutsos Epidemic spreading in real networks: An eigenvalue viewpoint, In Proc. Symp. Reliable Distributed Systems, 2003. Proceedings. 22nd International Symposium on, pages 25–34. IEEE, 2003.
[63]	V. Zagrebnov, Comments on the Chernoff $\sqrt{n} $ -lemma, In J. Dittrich, H. Kovařík, and A. Laptev, editors, Functional analysis and operator theory for quantum physics, EMS Series of Congress Reports, pages 565–573, (2017).