Matrix power inequalities and the number of walks in graphs
作者： Hanjo Täubig , Jeremias Weihmann
DOI: 10.1016/J.DAM.2013.10.002
关键词:
摘要: We unify and generalize several inequalities for the number w"k of walks length k in graphs, entry sum matrix powers. First, we present a weighted sandwich theorem Hermitian matrices which generalizes by Marcus Newman further our former unification undirected graphs Lagarias et al. Dress Gutman. The new inequality uses an arbitrary nonnegative weighting indices (vertices) allows to apply index (vertex) subsets (i.e., considering w"k(S,S) that start at vertex given subset S end within same subset). also deduce stronger variation case positive-semidefinite another Newman. Further, show similar symmetric is generalization walk numbers Erdos Simonovits, Gutman, Ilic Stevanovic. In last part, lower bounds spectral radius adjacency upper energy graphs.
acm.org
sci-hub.se 参考文章(33)
Sebastian M. Cioabă, Some Applications of Eigenvalues of Graphs Structural Analysis of Complex Networks. pp. 357- 379 ,(2011) , 10.1007/978-0-8176-4789-6_14
Lothar Von Collatz, Ulrich Sinogowitz, Spektren endlicher grafen Abhandlungen Aus Dem Mathematischen Seminar Der Universitat Hamburg. ,vol. 21, pp. 63- 77 ,(1957) , 10.1007/BF02941924
Bojan Mohar, Svatopluk Poljak, Eigenvalues in Combinatorial Optimization Institute for Mathematics and Its Applications. ,vol. 50, pp. 107- 151 ,(1993) , 10.1007/978-1-4613-8354-3_5
Piet Van Mieghem, Graph Spectra for Complex Networks ,(2010)
A. Ganesh, L. Massoulie, D. Towsley, The effect of network topology on the spread of epidemics international conference on computer communications. ,vol. 2, pp. 1455- 1466 ,(2005) , 10.1109/INFCOM.2005.1498374
M. Hofmeister, Spectral Radius and Degree Sequence Mathematische Nachrichten. ,vol. 139, pp. 37- 44 ,(1988) , 10.1002/MANA.19881390105
Herbert S Wilf, Spectral bounds for the clique and independence numbers of graphs Journal of Combinatorial Theory, Series B. ,vol. 40, pp. 113- 117 ,(1986) , 10.1016/0095-8956(86)90069-9
E. E. Doberkat, A Hyper-Volume SIAM Review. ,vol. 26, pp. 580- 580 ,(1984) , 10.1137/1026111
Yuan Hong, Xiao-Dong Zhang, Sharp upper and lower bounds for largest eigenvalue of the Laplacian matrices of trees Discrete Mathematics. ,vol. 296, pp. 187- 197 ,(2005) , 10.1016/J.DISC.2005.04.001
Aimei Yu, Mei Lu, Feng Tian, On the spectral radius of graphs Linear Algebra and its Applications. ,vol. 387, pp. 41- 49 ,(2004) , 10.1016/J.LAA.2004.01.020