Inequalities for the number of walks in graphs. (English) Zbl 1275.05028
Summary: 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 deduce the inequality \(w _{2a+c }\cdot w _{2(a+b)+c }\leq w _{2a }\cdot w _{2(a+b+c)}\), 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 _{2a+c }(v,v)\cdot w _{2(a+b)+c }(v,v)\leq w _{2a }(v,v)\cdot w _{2(a+b+c)}(v,v)\) for the number \(w _{k }(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_{2\ell+p}^{k}\leq w_{2\ell+pk}\cdot w_{2\ell}^{k-1}\), 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.
In the second part, we provide a new family of lower bounds for the largest eigenvalue \(\lambda _{1}\) 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.
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 _{a+b }\cdot w _{a+b+c }\leq w _{a }\cdot w _{a+2b+c }\) does not hold even in very restricted cases like \(w _{1}\cdot w _{2}\leq w _{0}\cdot w _{3}\) (i.e., \(\bar{d}\cdot w_{2}\leq 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 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 _{1}\cdot w _{4}\leq w _{0}\cdot w _{5}\) (i.e., \(\bar{d}\cdot w_{4}\leq w_{5}\)) for trees and conclude with a corresponding conjecture for longer walks.
In the second part, we provide a new family of lower bounds for the largest eigenvalue \(\lambda _{1}\) 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.
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 _{a+b }\cdot w _{a+b+c }\leq w _{a }\cdot w _{a+2b+c }\) does not hold even in very restricted cases like \(w _{1}\cdot w _{2}\leq w _{0}\cdot w _{3}\) (i.e., \(\bar{d}\cdot w_{2}\leq 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 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 _{1}\cdot w _{4}\leq w _{0}\cdot w _{5}\) (i.e., \(\bar{d}\cdot w_{4}\leq w_{5}\)) for trees and conclude with a corresponding conjecture for longer walks.
MSC:
| 05C30 | Enumeration in graph theory |
| 05C38 | Paths and cycles |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C81 | Random walks on graphs |
| 05C99 | Graph theory |
References:
| [1] | Ahlswede, R., Katona, G.O.H.: Graphs with maximal number of adjacent pairs of edges. Acta Math. Acad. Sci. Hung. 32(1-2), 97-120 (1978) · Zbl 0386.05036 · doi:10.1007/BF01902206 |
| [2] | Alon, N., Feige, U., Wigderson, A., Zuckerman, D.: Derandomized graph products. Comput. Complex. 5(1), 60-75 (1995) · Zbl 0816.60070 · doi:10.1007/BF01277956 |
| [3] | Blakley, G.R., Dixon, R.D.: Hölder type inequalities in cones. J. Math. Anal. Appl. 14(1), 1-4 (1966) · Zbl 0142.27004 · doi:10.1016/0022-247X(66)90056-4 |
| [4] | Blakley, G.R., Roy, P.: A Hölder type inequality for symmetric matrices with nonnegative entries. Proc. Am. Math. Soc. 16(6), 1244-1245 (1965) · Zbl 0142.27003 |
| [5] | Chakrabarti, D., Wang, Y., Wang, C., Leskovec, J., Faloutsos, C.: Epidemic thresholds in real networks. ACM Trans. Inf. Syst. Secur. 10(4), 13:1-13:26 (2008) · doi:10.1145/1284680.1284681 |
| [6] | Chung, F.R.K.: Spectral Graph Theory. Regional Conference Series in Mathematics, vol. 92. Am. Math. Soc., Providence (1997) · Zbl 0867.05046 |
| [7] | Cioabă, S. M.; Dehmer, M. (ed.), Some applications of eigenvalues of graphs, 357-379 (2011), Basel · Zbl 1221.05231 · doi:10.1007/978-0-8176-4789-6_14 |
| [8] | Collatz, L., Sinogowitz, U.: Spektren endlicher Grafen. Abh. Math. Semin. Univ. Hamb. 21(1), 63-77 (1957) · Zbl 0077.36704 · doi:10.1007/BF02941924 |
| [9] | Cvetković, D.M.: The generating function for variations with restrictions and paths of the graph and self-complementary graphs. Univ. Beog., Publ. Elektrotehn. Fak., Ser. Mat. Fiz. 320-328(322), 27-34 (1970) · Zbl 0204.24501 |
| [10] | Cvetković, D.M.: Graphs and their spectra. Univ. Beog., Publ. Elektrotehn. Fak., Ser. Mat. Fiz. 354-456(354), 1-50 (1971) · Zbl 0238.05102 |
| [11] | Cvetković, D. M., Applications of graph spectra: An introduction to the literature, No. 13(21), 7-31 (2009), Belgrade · Zbl 1265.05002 |
| [12] | Cvetković, D.M., Doob, M., Gutman, I., Torgašev, A.: Recent Results in the Theory of Graph Spectra. Annals of Discrete Mathematics, vol. 36. North-Holland, Amsterdam (1988) · Zbl 0634.05054 |
| [13] | Cvetković, D.M., Doob, M., Sachs, H.: Spectra of Graphs—Theory and Applications. Deutscher Verlag der Wissenschaften, Berlin (1979) |
| [14] | Cvetković, D.M., Rowlinson, P.: The largest eigenvalue of a graph: A survey. Linear Multilinear Algebra 28(1), 3-33 (1990) · Zbl 0744.05031 · doi:10.1080/03081089008818026 |
| [15] | Cvetković, D.M., Rowlinson, P., Simić, S.K.: Eigenspaces of Graphs. Encyclopedia of Mathematics and Its Applications, vol. 66. Cambridge University Press, Cambridge (1997) · Zbl 0878.05057 · doi:10.1017/CBO9781139086547 |
| [16] | De Caen, D.: An upper bound on the sum of squares of degrees in a graph. Discrete Math. 185, 245-248 (1998) · Zbl 0955.05059 · doi:10.1016/S0012-365X(97)00213-6 |
| [17] | Dress, A., Gutman, I.: The number of walks in a graph. Appl. Math. Lett. 16(5), 797-801 (2003) · Zbl 1039.05043 · doi:10.1016/S0893-9659(03)00085-5 |
| [18] | Erdős, P., Simonovits, M.: Compactness results in extremal graph theory. Combinatorica 2(3), 275-288 (1982) · Zbl 0508.05043 · doi:10.1007/BF02579234 |
| [19] | Feige, U., Kortsarz, G., Peleg, D.: The dense k-subgraph problem. Algorithmica 29(3), 410-421 (2001) · Zbl 0969.68117 · doi:10.1007/s004530010050 |
| [20] | Fiol, M.À., Garriga, E.: Number of walks and degree powers in a graph. Discrete Math. 309(8), 2613-2614 (2009) · Zbl 1228.05171 · doi:10.1016/j.disc.2008.03.025 |
| [21] | Gutman, I., The energy of a graph: Old and new results, 196-211 (2001), Berlin · Zbl 0974.05054 |
| [22] | Hansen, P., Vukičević, D.: Comparing the Zagreb indices. Croat. Chem. Acta 80(2), 165-168 (2007) |
| [23] | Harary, F., Schwenk, A.J.: The spectral approach to determining the number of walks in a graph. Pac. J. Math. 80(2), 443-449 (1979) · Zbl 0417.05032 · doi:10.2140/pjm.1979.80.443 |
| [24] | Hemmecke, R., Kosub, S., Mayr, E.W., Täubig, H., Weihmann, J.: Inequalities for the number of walks in trees and general graphs and a generalization of a theorem of Erdős and Simonovits. Technical Report TUM-I1109, Department of Computer Science, Technische Universität München (2011) · Zbl 1430.05054 |
| [25] | Hemmecke, R.; Kosub, S.; Mayr, E. W.; Täubig, H.; Weihmann, J., Inequalities for the number of walks in graphs, 26-39 (2012), Philadelphia · Zbl 1430.05054 |
| [26] | Hoffman, A.J.: Three observations on nonnegative matrices. J. Res. Natl. Bur. Stand. B, Math. Math. Phys. 71(1), 39-41 (1967) · Zbl 0153.05103 · doi:10.6028/jres.071B.007 |
| [27] | Hoffman, A. J.; Harris, B. (ed.), On eigenvalues and colorings of graphs, 79-91 (1970), San Diego · Zbl 0221.05061 |
| [28] | Hofmeister, M.: Spectral radius and degree sequence. Math. Nachr. 139(1), 37-44 (1988) · Zbl 0695.05046 · doi:10.1002/mana.19881390105 |
| [29] | Hofmeister, M.: A note on almost regular graphs. Math. Nachr. 166(1), 259-262 (1994) · Zbl 0830.05045 · doi:10.1002/mana.19941660119 |
| [30] | Hong, Y., Zhang, X.D.: Sharp upper and lower bounds for largest eigenvalue of the Laplacian matrices of trees. Discrete Math. 296(2-3), 187-197 (2005) · Zbl 1068.05044 · doi:10.1016/j.disc.2005.04.001 |
| [31] | Hou, Y., Tang, Z., Woo, C.: On the spectral radius, k-degree and the upper bound of energy in a graph. MATCH Commun. Math. Comput. Chem. 57(2), 341-350 (2007) · Zbl 1150.05025 |
| [32] | Hu, S.: A sharp lower bound of the spectral radius of simple graphs. Appl. Anal. Discrete Math. 3(2), 379-385 (2009) · Zbl 1199.05223 · doi:10.2298/AADM0902379S |
| [33] | Ilić, A., Stevanović, D.: On comparing Zagreb indices. MATCH Commun. Math. Comput. Chem. 62(3), 681-687 (2009) · Zbl 1274.05095 |
| [34] | Kosub, S.; Brandes, U. (ed.); Erlebach, T. (ed.), Local density, No. 3418, 112-142 (2005), Berlin · Zbl 1118.68332 · doi:10.1007/978-3-540-31955-9_6 |
| [35] | Lagarias, J.C., Mazo, J.E., Shepp, L.A., McKay, B.D.: An inequality for walks in a graph. SIAM Rev. 25(3), 403 (1983) · doi:10.1137/1025084 |
| [36] | Lagarias, J.C., Mazo, J.E., Shepp, L.A., McKay, B.D.: An inequality for walks in a graph. SIAM Rev. 26(4), 580-582 (1984) · doi:10.1137/1026112 |
| [37] | Lewis, H.R., Papadimitriou, C.H.: Symmetric space-bounded computation. Theor. Comput. Sci. 19(2), 161-187 (1982) · Zbl 0491.68045 · doi:10.1016/0304-3975(82)90058-5 |
| [38] | London, D.: Inequalities in quadratic forms. Duke Math. J. 33(3), 511-522 (1966) · Zbl 0166.03901 · doi:10.1215/S0012-7094-66-03360-6 |
| [39] | London, D.: Two inequalities in nonnegative symmetric matrices. Pac. J. Math. 16(3), 515-536 (1966) · Zbl 0136.25001 · doi:10.2140/pjm.1966.16.515 |
| [40] | Marcus, M., Newman, M.: The sum of the elements of the powers of a matrix. Pac. J. Math. 12(2), 627-635 (1962) · Zbl 0111.01502 · doi:10.2140/pjm.1962.12.627 |
| [41] | McClelland, B.J.: Properties of the latent roots of a matrix: The estimation of π-electron energies. J. Chem. Phys. 54(2), 640-643 (1971) · doi:10.1063/1.1674889 |
| [42] | Mulholland, H.P., Smith, C.A.B.: An inequality arising in genetical theory. Am. Math. Mon. 66(8), 673-683 (1959) · Zbl 0094.00903 · doi:10.2307/2309342 |
| [43] | Mulholland, H.P., Smith, C.A.B.: Corrections: An inequality arising in genetical theory. Am. Math. Mon. 67(2), 161 (1960) · Zbl 0094.00903 · doi:10.2307/2308531 |
| [44] | Nikiforov, V.: Walks and the spectral radius of graphs. Linear Algebra Appl. 418(1), 257-268 (2006) · Zbl 1106.05065 · doi:10.1016/j.laa.2006.02.003 |
| [45] | Nikiforov, V.: The sum of the squares of degrees: Sharp asymptotics. Discrete Math. 307(24), 3187-3193 (2007) · Zbl 1127.05054 · doi:10.1016/j.disc.2007.03.019 |
| [46] | Nosal, E.: Eigenvalues of graphs. Master’s thesis, University of Calgary (1970) · Zbl 0235.05101 |
| [47] | Peled, U.N., Petreschi, R., Sterbini, A.: (n,e)-graphs with maximum sum of squares of degrees. J. Graph Theory 31(4), 283-295 (1999) · Zbl 0945.05035 · doi:10.1002/(SICI)1097-0118(199908)31:4<283::AID-JGT3>3.0.CO;2-H |
| [48] | Van Mieghem, P.: Graph Spectra for Complex Networks. Cambridge University Press, Cambridge (2011) · Zbl 1232.05128 |
| [49] | Vukičević, D., Graovac, A.: Comparing Zagreb M1 and M2 indices for acyclic molecules. MATCH Commun. Math. Comput. Chem. 57(3), 587-590 (2007) · Zbl 1142.05313 |
| [50] | Wang, H.: Extremal trees with given degree sequence for the Randić index. Discrete Math. 308(15), 3407-3411 (2008) · Zbl 1160.05016 · doi:10.1016/j.disc.2007.06.026 |
| [51] | Wilf, H.S.: The eigenvalues of a graph and its chromatic number. J. Lond. Math. Soc. 42, 330-332 (1967) · Zbl 0144.45202 · doi:10.1112/jlms/s1-42.1.330 |
| [52] | Wilf, H.S.: Spectral bounds for the clique and independence numbers of graphs. J. Comb. Theory, Ser. B 40(1), 113-117 (1986) · Zbl 0598.05047 · doi:10.1016/0095-8956(86)90069-9 |
| [53] | Yu, A., Lu, M., Tian, F.: On the spectral radius of graphs. Linear Algebra Appl. 387, 41-49 (2004) · Zbl 1041.05051 · doi:10.1016/j.laa.2004.01.020 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
