Login
- Title:
Inequalities for the Number of Walks, the Spectral Radius, and the Energy of Graphs
- Author(s):
- Hanjo Täubig; Jeremias Weihmann
- Abstract:
- We unify and generalize several inequalities for the number~$w_k$ of walks of length~$k$ in graphs. The new inequalities use an arbitrary nonnegative weighting of the vertices. This allows an application of the theorems to subsets of vertices, i.e., these inequalities consider the number $w_k(S,S)$ of walks of length~$k$ that start at a vertex of a given vertex subset~$S$ and that end within the same subset. In particular, we show a weighted sandwich theorem for Hermitian matrices which generalizes a theorem by Marcus and Newman and which implies $w_{2a+c}(S,S) \cdot w_{2a+2b+c}(S,S) \leq w_{2a}(S,S) \cdot w_{2(a+b+c)}(S,S)$, a unification and generalization of inequalities by Lagarias et~al.\ and by Dress \& Gutman. Further, we show a theorem for nonnegative symmetric matrices that implies $w_{2\ell+p}(S,S)^k \leq w_{2\ell}(S,S)^{k-1}\cdot w_{2\ell+pk}(S,S)$, which is a unification and generalization of inequalities by Erd{\H{o}}s~\& Simonovits, by Dress~\& Gutman, and by Ili{\'c}~\& Stevanovi{\'c}. Both results can be translated into corresponding forms for matrix or graph densities. In the end, these results are used to generalize lower bounds for the spectral radius and upper bounds for the energy of graphs.
- Keywords:
- inequalities, undirected graph, number of walks, hermitian matrix, nonnegative matrix, matrix powers, sum of elements, spectral radius, largest eigenvalue, graph energy
- Year:
- 2012
- Language:
- en
BibTeX