## Abstract

We investigate the growth of the number w_{k} of walks of length k in undirected graphs as well as related inequalities. In the first part, we derive the inequalities w_{2a+c} · w_{2(a+b)+c} ≤ w_{2a} · w_{2(a+b+c)} and W_{2a+c}(υ,υ) · w_{2(a+b)+c}(υ,υ) ≤ w_{2a}(υ,υ) · w_{2(a+b+c)}(υ,υ) for the number w_{k}(υ,υ) of closed walks of length k starting at a given vertex v. The first is a direct implication of a matrix inequality by Marcus and Newman and generalizes two inequalities by Lagarias et al. and Dress & Gutman. We then use an inequality of Blakley and Dixon to show the inequality w_{2ℓ+p}^{k} p ≤ w_{2ℓ+pk} · w_{2ℓ}^{k-1} which also generalizes the inequality by Dress and Gutman and also an inequality by Erdos and Simonovits. Both results can be translated directly into the corresponding forms using the higher order densities, which extends former results. In the second part, we provide a new family of lower bounds for the largest eigenvalue λ_{1} of the adjacency matrix based on closed walks and apply the before mentioned inequalities to show monotonicity in this and a related family of lower bounds of Nikiforov. This leads to generalized upper bounds for the energy of graphs. In the third part, we demonstrate that a further natural generalization of the inequality w_{2a+c} · w_{2(a+b)+c} ≤ w_{2a} · w_{2(a+6+c)} is not valid for general graphs. We show that w_{a+b} · w_{a+b+c} ≤ w_{a} · w_{a+2b+c} does not hold even in very restricted cases like w_{1} · w_{2} ≤ w_{0} · w_{3} (i.e., d¯ · w_{2} ≤ w_{3}) in the context of bipartite or cycle free graphs. In contrast, we show that surprisingly this inequality is always satisfied for trees and show how to construct worst-case instances (regarding the difference of both sides of the inequality) for a given degree sequence. We also provide a proof for the inequality w_{1} · w_{4} ≤ w_{0} · w_{5} (i.e., d¯·w_{4} ≤ w_{5}) for trees and conclude with a corresponding conjecture for longer walks.

Originalsprache | Englisch |
---|---|

Titel | 9th Meeting on Analytic Algorithmics and Combinatorics 2012, ANALCO 2012 |

Herausgeber (Verlag) | Society for Industrial and Applied Mathematics Publications |

Seiten | 26-39 |

Seitenumfang | 14 |

ISBN (elektronisch) | 9781618396235 |

DOIs | |

Publikationsstatus | Veröffentlicht - 2012 |

Veranstaltung | 9th Meeting on Analytic Algorithmics and Combinatorics, ANALCO 2012 - Kyoto, Japan Dauer: 16 Jan. 2012 → … |

### Publikationsreihe

Name | 9th Meeting on Analytic Algorithmics and Combinatorics 2012, ANALCO 2012 |
---|

### Konferenz

Konferenz | 9th Meeting on Analytic Algorithmics and Combinatorics, ANALCO 2012 |
---|---|

Land/Gebiet | Japan |

Ort | Kyoto |

Zeitraum | 16/01/12 → … |