Let G=(V,E) be a simple graph, μ(G) be the highest eigenvalue of its adjacency matrix and wk denote the number of walks of lenght k (≥0). In literature lower bounds for μ(G) have been given in terms of the ratio w_(k+l)/w_k when k is even and for each l. In this work we will show that for regular, harmonic, semiregular and pseudosemiregular graphs the ratio w_(k+l)/w_k gives a bound for μ(G) also when k is odd. In particular for regular and harmonic graphs, for each k, l it holds that μ(G)=√(l&w_(k+l)/w_k ). For semiregular and pseudosemiregular graphs if k is odd and l is even then μ(G)=√(l&w_(k+l)/w_k ), while if both k and l are odd μ(G)<√(l&w_(k+l)/w_k ) obtaining an upper bound for μ(G)
Ceccarossi, G. L., On the highest eigenvalue and the number of walks for particular graphs, <<Working Paper Dipartimento di Discipline Matematiche, Finanza Matematica ed Econometria - Università Cattolica del Sacro Cuore>>, 2014; 2014 (14/8): 1-20 [http://hdl.handle.net/10807/65149]
On the highest eigenvalue and the number of walks for particular graphs
Ceccarossi, Guido Luigi
2014
Abstract
Let G=(V,E) be a simple graph, μ(G) be the highest eigenvalue of its adjacency matrix and wk denote the number of walks of lenght k (≥0). In literature lower bounds for μ(G) have been given in terms of the ratio w_(k+l)/w_k when k is even and for each l. In this work we will show that for regular, harmonic, semiregular and pseudosemiregular graphs the ratio w_(k+l)/w_k gives a bound for μ(G) also when k is odd. In particular for regular and harmonic graphs, for each k, l it holds that μ(G)=√(l&w_(k+l)/w_k ). For semiregular and pseudosemiregular graphs if k is odd and l is even then μ(G)=√(l&w_(k+l)/w_k ), while if both k and l are odd μ(G)<√(l&w_(k+l)/w_k ) obtaining an upper bound for μ(G)I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.