Inequalities for the number of walks in graphs

DOI10.1007/s00453-013-9766-3zbMath1275.05028OpenAlexW2000198292MaRDI QIDQ378237

Jeremias Weihmann, Hanjo Täubig, Raymond Hemmecke, Ernst W. Mayr, Sven Kosub

Publication date: 11 November 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9766-3

zbMATH Keywords

inequalitiesspectral radiusgraph energygrowth of the number of walks

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (05C99) Random walks on graphs (05C81)

Related Items

A path forward: tropicalization in extremal combinatorics, Matrix power inequalities and the number of walks in graphs, Chebyshev's Sum Inequality and the Zagreb Indices Inequality, Basic trigonometric power sums with applications, Comparing large-scale graphs based on quantum probability theory, On majorization of closed walk vectors of trees with given degree sequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The spectral approach to determining the number of walks in a graph
• Spektren endlicher Grafen
• Walks and the spectral radius of graphs
• Extremal trees with given degree sequence for the Randić index
• Number of walks and degree powers in a graph
• Spectral bounds for the clique and independence numbers of graphs
• The sum of the elements of the powers of a matrix
• Symmetric space-bounded computation
• Recent results in the theory of graph spectra
• The number of walks in a graph
• On the spectral radius of graphs
• An upper bound on the sum of squares of degrees in a graph
• Compactness results in extremal graph theory
• Derandomized graph products
• The sum of the squares of degrees: sharp asymptotics
• Sharp upper and lower bounds for largest eigenvalue of the Laplacian matrices of trees
• Two inequalities in nonnegative symmetric matrices
• Hölder type inequalities in cones
• Inequalities in quadratic forms
• Some Applications of Eigenvalues of Graphs
• An Inequality Arising in Genetical Theory
• Spectral Radius and Degree Sequence
• A sharp lower bound of the spectral radius of simple graphs
• On comparing Zagreb indices
• Graphs with maximal number of adjacent pairs of edges
• The largest eigenvalue of a graph: A survey
• A Note on Almost Regular Graphs
• Inequalities for the Number of Walks in Graphs
• A Holder Type Inequality for Symmetric Matrices with Nonnegative Entries
• The Eigenvalues of a Graph and Its Chromatic Number
• Three observations on nonnegative matrices
• Network Analysis
• The dense \(k\)-subgraph problem