Inequalities for the number of walks in graphs

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

TÄUBIG, Hanjo, Jeremias WEIHMANN, Sven KOSUB, Raymond HEMMECKE, Ernst W. MAYR, 2013. Inequalities for the number of walks in graphs. In: Algorithmica. 66(4), pp. 804-828. ISSN 0178-4617. eISSN 1432-0541. Available under: doi: 10.1007/s00453-013-9766-3

@article{Taubig2013Inequ-26480, title={Inequalities for the number of walks in graphs}, year={2013}, doi={10.1007/s00453-013-9766-3}, number={4}, volume={66}, issn={0178-4617}, journal={Algorithmica}, pages={804--828}, author={Täubig, Hanjo and Weihmann, Jeremias and Kosub, Sven and Hemmecke, Raymond and Mayr, Ernst W.} }

We investigate the growth of the number w<sub>k</sub> of walks of length k in undirected graphs as well as related inequalities. In the first part, we deduce the inequality w<sub>2a+c</sub>⋅w<sub>2(a+b)+c</sub> ≤w<sub>2a</sub>⋅w<sub>2(a+b+c)</sub>, which we call the Sandwich Theorem. It unifies and generalizes an inequality by Lagarias et al. and an inequality by Dress and Gutman. In the same way, we derive the inequality w<sub>2a+c</sub>(v,v⋅w<sub>2(a+b)+c</sub>(v,v)≤w<sub>2a</sub>(v,v)⋅w<sub>2(a+b+c)</sub>(v,v) for the number w<sub>k</sub>(v,v) of closed walks of length k starting at a given vertex v. We then use a theorem of Blakley and Dixon to show w<sup>k</sup><sub>2ℓ+p</sub>≤w<sub>2ℓ+pk</sub>⋅w<sup>k−1</sup><sub>2ℓ</sub> , which unifies and generalizes an inequality by Erdős and Simonovits and, again, the inequality by Dress and Gutman. Both results can be translated directly into the corresponding forms using the higher order densities, which extends former results.<br />In the second part, we provide a new family of lower bounds for the largest eigenvalue λ<sub>1</sub> of the adjacency matrix based on closed walks. We apply the Sandwich Theorem 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.<br />In the third part, we demonstrate that a further natural generalization of the Sandwich Theorem is not valid for general graphs. We show that the inequality w<sub>a+b</sub>⋅w<sub>a+b+c</sub>≤w<sub>a</sub>⋅w<sub>a+2b+c</sub> does not hold even in very restricted cases like w<sub>1</sub>⋅w<sub>2</sub>≤w<sub>0</sub>⋅w<sub>3</sub> (i.e., d¯⋅w<sub>2</sub>≤w<sub>3</sub>) in the context of bipartite or cycle free graphs. In contrast, we show that surprisingly this inequality is always satisfied for trees and we show how to construct worst-case instances (regarding the difference of both sides of the inequality) for a given degree sequence. We also prove the inequality w<sub>1</sub>⋅w<sub>4</sub>≤w<sub>0</sub>⋅w<sub>5</sub> (i.e., d¯⋅w<sub>4</sub>≤w<sub>5</sub>) for trees and conclude with a corresponding conjecture for longer walks. Inequalities for the number of walks in graphs eng Mayr, Ernst W. 2013 2014-02-19T13:46:00Z 2014-02-19T13:46:00Z Kosub, Sven Hemmecke, Raymond Täubig, Hanjo Täubig, Hanjo Algorithmica ; 66 (2013), 4. - S. 804-828 Mayr, Ernst W. Weihmann, Jeremias Hemmecke, Raymond terms-of-use Kosub, Sven Weihmann, Jeremias

This item appears in the following Collection(s)

Search KOPS


My Account