Dynamical systems associated with adjacency matrices

Previous Article
Explosive synchronization in mono and multilayer networks
DCDS-B Home
This Issue
Next Article
Evolving multiplayer networks: Modelling the evolution of cooperation in a mobile population

July 2018, 23(5): 1945-1973. doi: 10.3934/dcdsb.2018190

Dynamical systems associated with adjacency matrices

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

Received February 2017 Revised September 2017 Published May 2018

Fund Project: 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"

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: Adjacency matrix, line graphs, infinite graphs, evolution equations.

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

Citation: Delio Mugnolo. Dynamical systems associated with adjacency matrices. Discrete & Continuous Dynamical Systems - B, 2018, 23 (5) : 1945-1973. doi: 10.3934/dcdsb.2018190

References:

[1]	H. Baloudi, S. Golénia and A. Jeribi. The adjacency matrix and the discrete Laplacian acting on forms, arXiv: 1505.06109 2015.Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[5]	A. E. Brouwer and W. H. Haemers. Spectra of Graphs Universitext. Springer-Verlag, Berlin, 2012. doi: 10.1007/978-1-4614-1939-6. Google Scholar
[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. Google Scholar
[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. Google Scholar
[8]	D. Cartwright and W. Woess, The spectrum of the averaging operator on a network (metric graph), Illinois J. Math., 51 (2007), 805-830. Google Scholar
[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. Google Scholar
[10]	R. Chill and E. Fašangová, Gradient Systems MatFyzPress, Prague, 2010.Google Scholar
[11]	F. Chung and S.-T. Yau, Coverings, heat kernels and spanning trees, Electron. J. Combin. , 6 (1998), Research Paper 12, 21 pp. Google Scholar
[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. Google Scholar
[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. Google Scholar
[14]	L. Collatz and U. Sinogowitz, Spektren endlicher grafen, Abh. Math. Seminar Univ. Hamburg, 21 (1957), 63-77. doi: 10.1007/BF02941924. Google Scholar
[15]	D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs – Theory and Applications, Pure Appl. Math. Academic Press, New York-London, 1980. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[20]	E. B. Davies, Linear Operators and Their Spectra, Cambridge Univ. Press, Cambridge, 2007. doi: 10.1017/CBO9780511618864. Google Scholar
[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. Google Scholar
[22]	R. Diestel, Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 2005. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[28]	M. Fiedler, Algebraic connectivity of graphs, Czech. Math. J., 23 (1973), 298-305. Google Scholar
[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. Google Scholar
[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. Google Scholar
[31]	D. F. Gleich, PageRank beyond the Web, SIAM Review, 57 (2015), 321-363. doi: 10.1137/140976649. Google Scholar
[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. Google Scholar
[33]	C. Godsil, State transfer on graphs, Disc. Math., 312 (2012), 129-147. doi: 10.1016/j.disc.2011.06.032. Google Scholar
[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. Google Scholar
[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. Google Scholar
[36]	M. Haase, Functional Analysis – An Elementary Introduction, Amer. Math. Soc., Providence, RI, 2014. Google Scholar
[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. Google Scholar
[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. Google Scholar
[39]	F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969. Google Scholar
[40]	R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge Univ. Press, Cambridge, 1991. doi: 10.1017/CBO9780511840371. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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.Google Scholar
[47]	A. Meyerowitz, Largest adjacency eigenvalue of line graphs, MathOverflow, http://www.mathoverflow.net/q/262340 (version: 2017-02-16).Google Scholar
[48]	B. Mohar, The spectrum of an infinite graph, Lin. Algebra Appl., 48 (1982), 245-256. doi: 10.1016/0024-3795(82)90111-2. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[55]	R. Nagel, editor. One-Parameter Semigroups of Positive Operators, volume 1184 of Lect. Notes Math. Springer-Verlag, Berlin, 1986.Google Scholar
[56]	E. M. Ouhabaz, Analysis of Heat Equations on Domains, volume 30 of Lond. Math. Soc. Monograph Series. Princeton Univ. Press, Princeton, NJ, 2005. Google Scholar
[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.Google Scholar
[58]	A. E. Taylor, Introduction to Functional Analysis, Wiley, New York, 1958. Google Scholar
[59]	G. Tinhofer, Graph isomorphism and theorems of Birkhoff type, Computing, 36 (1986), 285-300. doi: 10.1007/BF02240204. Google Scholar
[60]	P. van Mieghem, The $N$ -intertwined SIS epidemic network model, Computing, 93 (2011), 147-169. doi: 10.1007/s00607-011-0155-y. Google Scholar
[61]	P. Van Mieghem, J. Omic and R. Kooij, Virus spread in networks, IEEE/ACM Trans. Networking, 17 (2009), 1-14. Google Scholar
[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.Google Scholar
[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). Google Scholar

show all references

References:

[1]	H. Baloudi, S. Golénia and A. Jeribi. The adjacency matrix and the discrete Laplacian acting on forms, arXiv: 1505.06109 2015.Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[5]	A. E. Brouwer and W. H. Haemers. Spectra of Graphs Universitext. Springer-Verlag, Berlin, 2012. doi: 10.1007/978-1-4614-1939-6. Google Scholar
[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. Google Scholar
[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. Google Scholar
[8]	D. Cartwright and W. Woess, The spectrum of the averaging operator on a network (metric graph), Illinois J. Math., 51 (2007), 805-830. Google Scholar
[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. Google Scholar
[10]	R. Chill and E. Fašangová, Gradient Systems MatFyzPress, Prague, 2010.Google Scholar
[11]	F. Chung and S.-T. Yau, Coverings, heat kernels and spanning trees, Electron. J. Combin. , 6 (1998), Research Paper 12, 21 pp. Google Scholar
[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. Google Scholar
[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. Google Scholar
[14]	L. Collatz and U. Sinogowitz, Spektren endlicher grafen, Abh. Math. Seminar Univ. Hamburg, 21 (1957), 63-77. doi: 10.1007/BF02941924. Google Scholar
[15]	D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs – Theory and Applications, Pure Appl. Math. Academic Press, New York-London, 1980. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[20]	E. B. Davies, Linear Operators and Their Spectra, Cambridge Univ. Press, Cambridge, 2007. doi: 10.1017/CBO9780511618864. Google Scholar
[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. Google Scholar
[22]	R. Diestel, Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 2005. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[28]	M. Fiedler, Algebraic connectivity of graphs, Czech. Math. J., 23 (1973), 298-305. Google Scholar
[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. Google Scholar
[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. Google Scholar
[31]	D. F. Gleich, PageRank beyond the Web, SIAM Review, 57 (2015), 321-363. doi: 10.1137/140976649. Google Scholar
[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. Google Scholar
[33]	C. Godsil, State transfer on graphs, Disc. Math., 312 (2012), 129-147. doi: 10.1016/j.disc.2011.06.032. Google Scholar
[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. Google Scholar
[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. Google Scholar
[36]	M. Haase, Functional Analysis – An Elementary Introduction, Amer. Math. Soc., Providence, RI, 2014. Google Scholar
[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. Google Scholar
[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. Google Scholar
[39]	F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969. Google Scholar
[40]	R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge Univ. Press, Cambridge, 1991. doi: 10.1017/CBO9780511840371. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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.Google Scholar
[47]	A. Meyerowitz, Largest adjacency eigenvalue of line graphs, MathOverflow, http://www.mathoverflow.net/q/262340 (version: 2017-02-16).Google Scholar
[48]	B. Mohar, The spectrum of an infinite graph, Lin. Algebra Appl., 48 (1982), 245-256. doi: 10.1016/0024-3795(82)90111-2. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[55]	R. Nagel, editor. One-Parameter Semigroups of Positive Operators, volume 1184 of Lect. Notes Math. Springer-Verlag, Berlin, 1986.Google Scholar
[56]	E. M. Ouhabaz, Analysis of Heat Equations on Domains, volume 30 of Lond. Math. Soc. Monograph Series. Princeton Univ. Press, Princeton, NJ, 2005. Google Scholar
[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.Google Scholar
[58]	A. E. Taylor, Introduction to Functional Analysis, Wiley, New York, 1958. Google Scholar
[59]	G. Tinhofer, Graph isomorphism and theorems of Birkhoff type, Computing, 36 (1986), 285-300. doi: 10.1007/BF02240204. Google Scholar
[60]	P. van Mieghem, The $N$ -intertwined SIS epidemic network model, Computing, 93 (2011), 147-169. doi: 10.1007/s00607-011-0155-y. Google Scholar
[61]	P. Van Mieghem, J. Omic and R. Kooij, Virus spread in networks, IEEE/ACM Trans. Networking, 17 (2009), 1-14. Google Scholar
[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.Google Scholar
[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). Google Scholar

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

Figure Options

Download full-size image

Download as 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$

Figure Options

Download full-size image

Download as PowerPoint slide

[1]	Dina Ghinelli, Jennifer D. Key. Codes from incidence matrices and line graphs of Paley graphs. Advances in Mathematics of Communications, 2011, 5 (1) : 93-108. doi: 10.3934/amc.2011.5.93
[2]	Joachim von Below, José A. Lubary. Isospectral infinite graphs and networks and infinite eigenvalue multiplicities. Networks & Heterogeneous Media, 2009, 4 (3) : 453-468. doi: 10.3934/nhm.2009.4.453
[3]	Robert Carlson. Dirichlet to Neumann maps for infinite quantum graphs. Networks & Heterogeneous Media, 2012, 7 (3) : 483-501. doi: 10.3934/nhm.2012.7.483
[4]	Jennifer D. Key, Washiela Fish, Eric Mwambene. Codes from the incidence matrices and line graphs of Hamming graphs $H^k(n,2)$ for $k \geq 2$. Advances in Mathematics of Communications, 2011, 5 (2) : 373-394. doi: 10.3934/amc.2011.5.373
[5]	Regino Criado, Julio Flores, Alejandro J. García del Amo, Miguel Romance. Structural properties of the line-graphs associated to directed networks. Networks & Heterogeneous Media, 2012, 7 (3) : 373-384. doi: 10.3934/nhm.2012.7.373
[6]	A. Procacci, Benedetto Scoppola. Convergent expansions for random cluster model with $q>0$ on infinite graphs. Communications on Pure & Applied Analysis, 2008, 7 (5) : 1145-1178. doi: 10.3934/cpaa.2008.7.1145
[7]	Shui-Nee Chow, Wuchen Li, Haomin Zhou. Entropy dissipation of Fokker-Planck equations on graphs. Discrete & Continuous Dynamical Systems - A, 2018, 38 (10) : 4929-4950. doi: 10.3934/dcds.2018215
[8]	Alexander Pankov. Nonlinear Schrödinger Equations on Periodic Metric Graphs. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 697-714. doi: 10.3934/dcds.2018030
[9]	Litao Guo, Bernard L. S. Lin. Vulnerability of super connected split graphs and bisplit graphs. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1179-1185. doi: 10.3934/dcdss.2019081
[10]	Srimathy Srinivasan, Andrew Thangaraj. Codes on planar Tanner graphs. Advances in Mathematics of Communications, 2012, 6 (2) : 131-163. doi: 10.3934/amc.2012.6.131
[11]	Cristina M. Ballantine. Ramanujan type graphs and bigraphs. Conference Publications, 2003, 2003 (Special) : 78-82. doi: 10.3934/proc.2003.2003.78
[12]	Daniele D'angeli, Alfredo Donno, Michel Matter, Tatiana Nagnibeda. Schreier graphs of the Basilica group. Journal of Modern Dynamics, 2010, 4 (1) : 167-205. doi: 10.3934/jmd.2010.4.167
[13]	Yong Lin, Gábor Lippner, Dan Mangoubi, Shing-Tung Yau. Nodal geometry of graphs on surfaces. Discrete & Continuous Dynamical Systems - A, 2010, 28 (3) : 1291-1298. doi: 10.3934/dcds.2010.28.1291
[14]	Renato Iturriaga, Héctor Sánchez Morgado. The Lax-Oleinik semigroup on graphs. Networks & Heterogeneous Media, 2017, 12 (4) : 643-662. doi: 10.3934/nhm.2017026
[15]	Thomas Zaslavsky. Quasigroup associativity and biased expansion graphs. Electronic Research Announcements, 2006, 12: 13-18.
[16]	Joachim von Below, José A. Lubary. Stability implies constancy for fully autonomous reaction-diffusion-equations on finite metric graphs. Networks & Heterogeneous Media, 2018, 13 (4) : 691-717. doi: 10.3934/nhm.2018031
[17]	Jin Liang, James H. Liu, Ti-Jun Xiao. Condensing operators and periodic solutions of infinite delay impulsive evolution equations. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 475-485. doi: 10.3934/dcdss.2017023
[18]	Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907
[19]	Fabio Camilli, Adriano Festa, Silvia Tozza. A discrete Hughes model for pedestrian flow on graphs. Networks & Heterogeneous Media, 2017, 12 (1) : 93-112. doi: 10.3934/nhm.2017004
[20]	Luca Schenato, Sandro Zampieri. On rendezvous control with randomly switching communication graphs. Networks & Heterogeneous Media, 2007, 2 (4) : 627-646. doi: 10.3934/nhm.2007.2.627

2018 Impact Factor: 1.008

Tools

Metrics

Tools

Article outline

Figures and Tables

2018 Impact Factor: 1.008

Tools

Figures and Tables

2018 Impact Factor: 1.008

American Institute of Mathematical Sciences