Walks and the spectral radius of graphs

By Vladimir Nikiforov. 2005

119 citations recorded by the source corpus.

Abstract Given a graph G, write μ(G) for the largest eigenvalue of its adjacency matrix, ω(G) for its clique number, and wk(G) for the number of its k-walks. We prove that the inequalities w q + r ( G ) w q ( G ) ⩽ μ r ( G ) ⩽ ω ( G ) - 1 ω ( G ) w r ( G ) hold for all r > 0 and odd q > 0. We also generalize a number of other bounds on μ(G) and characterize semiregular and pseudo-regular graphs in spectral terms.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/05e80a5cda6de0562dad702b21385d3d17e34c47

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

The main eigenvalues of a graph: A survey (2007, methodology): “In [24], a harmonic graph without isolated vertices is called pseudo-regular; for any vertex v in such a graph, the mean degree of the neighbours of v is μ1.”
A survey on spectral conditions for some extremal graph problems (2021, background): “13 was later characterized in [150, Theorem 2]; see [145] for more discussions.”
Beyond graph energy: norms of graphs and matrices (2015, background): “However, inequality λ ≥ 2m/n is just one of the infinitely many lower bounds on λ in terms of walks, see [30] for details.”
Principal eigenvectors of irregular graphs (2007, background): “It follows from the results in [6] that the right hand-side of the previous inequality is monotonically increasing with k.”
Some new results in extremal graph theory (2011, background): “An infinite class of similar lower bounds is given in [70].”