Inequalities for the Number of Walks in Subdivision Graphs

We consider an undirected graph $G$ with $n$ vertices and $m$ edges that is modified by introducing an intermediate vertex on every edge. It has been shown by Ilic and Stevanovic that this subdivision graph $S_G$ satisfies the inequality $M_1(S_G)/(m+n)\le M_2(S_g)/(2m)$ for the Zagreb indices $M_1$ and $M_2$. This inequality can also be expressed as $w_1(S_G) w_2(S_G) \le w_0(S_G) w_3(S_G)$, where $w_k(G)$ denotes the number of $k$-step walks in $G$. Besides trees, this is another class of bipartite graphs where the inequality holds true. The aim of this paper is to show the inequalities $w_1(S_G) w_4(S_G) \le w_0(S_G) w_5(S_G)$ and $w_2(S_G) w_3(S_G) \le w_0(S_G) w_5(S_G)$. This raises the question whether the generalization $w_a(S_G) w_b(S_G) \le w_0(S_G) w_{a+b}(S_G)$ is satisfied for subdivision graphs.      «

We consider an undirected graph $G$ with $n$ vertices and $m$ edges that is modified by introducing an intermediate vertex on every edge. It has been shown by Ilic and Stevanovic that this subdivision graph $S_G$ satisfies the inequality $M_1(S_G)/(m+n)\le M_2(S_g)/(2m)$ for the Zagreb indices $M_1$ and $M_2$. This inequality can also be expressed as $w_1(S_G) w_2(S_G) \le w_0(S_G) w_3(S_G)$, where $w_k(G)$ denotes the number of $k$-step walks in $G$. Besides trees, this is another class...     »