Czechoslovak Mathematical Journal, Vol. 72, No. 3, pp. 783-799, 2022
Inequalities for real number sequences with applications in spectral graph theory
Emina Milovanović, Şerife Burcu Bozkurt Altındağ, Marjan Matejić, Igor Milovanović
Received April 25, 2021. Published online March 23, 2022.
Abstract: Let $a=(a_1,a_2,\ldots,a_n)$ be a nonincreasing sequence of positive real numbers. Denote by $S=\{1,2,\ldots,n\}$ the index set and by $J_k=\{I= \{ r_1,r_2,\ldots,r_k \}$, $1\leq r_1<r_2< \nobreak\cdots<r_k\leq n\}$ the set of all subsets of $S$ of cardinality $k$, $1\leq k\leq n-1$. In addition, denote by $a_I=a_{r_1}+a_{r_2}+\cdots+a_{r_k}$, $1\leq k\leq n-1$, $1\leq r_1<r_2<\cdots<r_k\leq n$, the sum of $k$ arbitrary elements of sequence $a$, where $a_{I_1}=a_1+a_2+\cdots+a_k$ and $a_{I_n}=a_{n-k+1}+a_{n-k+2}+\cdots+a_n$. We consider bounds of the quantities $RS_k(a)=a_{I_1}/a_{I_n}$, $LS_k(a)=a_{I_1}-a_{I_n}$ and $S_{k,\alpha}(a)=\sum_{I\in J_k}a_I^{\alpha}$ in terms of $A=\sum_{i=1}^na_i$ and $B=\sum_{i=1}^na_i^2$. Then we use the obtained results to generalize some results regarding Laplacian and normalized Laplacian eigenvalues of graphs.
Keywords: inequality; real number sequence; Laplacian eigenvalue of graph; normalized Laplacian eigenvalue
References: [1] E. Andrade, M. A. A. de Freitas, M. Robbiano, J. Rodriguez: New lower bounds for the Randić spread. Linear Algebra Appl. 544 (2018), 254-272. DOI 10.1016/j.laa.2017.07.037 | MR 3765785 | Zbl 1388.05108
[2] M. Bianchi, A. Cornaro, J. L. Palacios, A. Torriero: Bounds for the Kirchhoff index via majorization techniques. J. Math. Chem. 51 (2013), 569-587. DOI 10.1007/s10910-012-0103-x | MR 3017758 | Zbl 1327.05066
[3] S. K. Butler: Eigenvalues and Structures of Graphs: Ph.D. Thesis. University of California, San Diego (2008). MR 2711548
[4] M. Cavers, S. Fallat, S. Kirkland: On the normalized Laplacian energy and general Randić index $R_{-1}$ of graphs. Linear Algebra Appl. 433 (2010), 172-190. DOI 10.1016/j.laa.2010.02.002 | MR 2645076 | Zbl 1217.05138
[5] X. Chen, K. C. Das: Some results on the Laplacian spread of a graph. Linear Algebra Appl. 505 (2016), 245-260. DOI 10.1016/j.laa.2016.05.002 | MR 3506494 | Zbl 1338.05158
[6] X. Chen, J. Qian: Bounding the sum of powers of the Laplacian eigenvalues of graphs. Appl. Math., Ser. B (Engl. Ed.) 26 (2011), 142-150. DOI 10.1007/s11766-011-2732-4 | MR 2810546 | Zbl 1240.05186
[7] F. R. K. Chung: Spectral Graph Theory. Regional Conference Series in Mathematics 92. AMS, Providence (1997). DOI 10.1090/cbms/092 | MR 1421568 | Zbl 0867.05046
[8] C. S. Edwards: The largest vertex degree sum for a triangle in a graph. Bull. Lond. Math. Soc. 9 (1977), 203-208. DOI 10.1112/blms/9.2.203 | MR 0463005 | Zbl 0357.05058
[9] G. H. Fath-Tabar, A. R. Ashrafi: Some remarks on Laplacian eigenvalues and Laplacian energy of graphs. Math. Commun. 15 (2010), 443-451. MR 2814304 | Zbl 1206.05062
[10] F. Goldberg: Bounding the gap between extremal Laplacian eigenvalues of graphs. Linear Algebra Appl. 416 (2006), 68-74. DOI 10.1016/j.laa.2005.07.007 | MR 2232920 | Zbl 1107.05059
[11] R. Grone, R. Merris: The Laplacian spectrum of graph. II. SIAM J. Discrete Math. 7 (1994), 221-229. DOI 10.1137/S0895480191222653 | MR 1271994 | Zbl 0795.05092
[12] I. Gutman, N. Trinajstić: Graph theory and molecular orbitals. Total $\phi $-electron energy of alternant hydrocarbons. Chem. Phys. Lett. 17 (1972), 535-538. DOI 10.1016/0009-2614(72)85099-1
[13] M. Hakimi-Nezhaad, A. R. Ashrafi: A note on normalized Laplacian energy of graphs. J. Contemp. Math. Anal., Armen. Acad. Sci. 49 (2014), 207-211. DOI 10.3103/S106836231405001X | MR 3379554 | Zbl 1312.05082
[14] J. Huang, S. Li: On the normalized Laplacian spectrum, degree-Kirchhoff index and spanning trees of graphs. Bul. Aust. Math. Soc. 91 (2015), 353-367. DOI 10.1017/S0004972715000027 | MR 3338961 | Zbl 1326.05082
[15] J. L. W. V. Jensen: Sur les functions convexes et les inéqualités entre les valeurs moyennes. Acta Math. 30 (1906), 175-193. (In French.) DOI 10.1007/BF02418571 | MR 1555027 | JFM 37.0422.02
[16] J. G. Kemeny, J. L. Snell: Finite Markov Chains. The University Series in Undergraduate Mathematics. Van Nostrand, Princeton (1960). MR 0115196 | Zbl 0089.13704
[17] J. Li, J.-M. Guo, W. C. Shiu, Ş. B. B. Altındağ, D. Bozkurt: Bounding the sum of powers of normalized Laplacian eigenvalues of a graph. Appl. Math. Comput. 324 (2018), 82-92. DOI 10.1016/j.amc.2017.12.003 | MR 3743658 | Zbl 1426.05101
[18] R. Merris: Laplacian matrices of graphs: A survey. Linear Algebra Appl. 197-198 (1994), 143-176. DOI 10.1016/0024-3795(94)90486-3 | MR 1275613 | Zbl 0802.05053
[19] I. Ž. Milovanović, E. I. Milovanović, E. Glogić: Lower bounds of the Kirchhoff and degree Kirchhoff indices. Sci. Publ. State Univ. Novi Pazar, Ser. A, Appl. Math. Inf. Mech. 7 (2015), 25-31. DOI 10.5937/SPSUNP1501025M
[20] I. Ž. Milovanović, E. I. Milovanović, E. Glogić: On Laplacian eigenvalues of connected graphs. Czech. Math. J. 65 (2015), 529-535. DOI 10.1007/s10587-015-0191-4 | MR 3360442 | Zbl 1363.15016
[21] I. Ž. Milovanović, E. I. Milovanović: Bounds for the Kirchhoff and degree Kirchhoff indices. Bounds in Chemical Graph Theory: Mainstreams Mathematical Chemistry Monographs 20. University of Kragujevac, Kragujevac (2017), 93-119.
[22] D. S. Mitrinović, J. E. Pečarić, A. M. Fink: Classical and New Inequalities in Analysis. Mathematics and Its Applications. East European Series 61. Kluwer Academic Publishers, Dorchrecht (1993). DOI 10.1007/978-94-017-1043-5 | MR 1220224 | Zbl 0771.26009
[23] V. Nikiforov: The energy of graphs and matrices. J. Math. Anal. Appl. 326 (2007), 1472-1475. DOI 10.1016/j.jmaa.2006.03.072 | MR 2280998 | Zbl 1113.15016
[24] E. A. Nordhaus, J. W. Gaddum: On complementary graphs. Am. Math. Mon. 63 (1956), 175-177. DOI 10.2307/2306658 | MR 0078685 | Zbl 0070.18503
[25] N. Ozeki: On the estimation of the inequalities by the maximum, or minimum values. J. College Arts Sci. Chiba Univ. 5 (1968), 199-203. (In Japanese.) MR 0254198
[26] J. L. Palacios: Some inequalities for Laplacian descriptors via majorization. MATCH Commun. Math. Comput. Chem. 77 (2017), 189-194. MR 3645376 | Zbl 1466.92279
[27] J. L. Palacios, J. M. Renom: Broder and Karlin's formula for hitting times and the Kirchhoff index. Int. J. Quantum Chem. 111 (2011), 35-39. DOI 10.1002/qua.22396
[28] L. Shi: Bounds on Randić indices. Discr. Math. 309 (2009), 5238-5241. DOI 10.1016/j.disc.2009.03.036 | MR 2548924 | Zbl 1179.05039
[29] L. Shi, H. Wang: The Laplacian incidence energy of graphs. Linear Algebra Appl. 439 (2013), 4056-4062. DOI 10.1016/j.laa.2013.10.028 | MR 3133474 | Zbl 1282.05152
[30] Z. You, B. Liu: On the Laplacian spectral ratio of connected graphs. Appl. Math. Lett. 25 (2012), 1245-1250. DOI 10.1016/j.aml.2011.09.071 | MR 2947387 | Zbl 1248.05116
[31] Z. You, B. Liu: The Laplacian spread of graphs. Czech. Math. J. 62 (2012), 155-168. DOI 10.1007/s10587-012-0003-z | MR 2899742 | Zbl 1245.05089
[32] B. Zhou: On sum of powers of the Laplacian eigenvalues of graphs. Linear Algebra Appl. 429 (2008), 2239-2246. DOI 10.1016/j.laa.2008.06.023 | MR 2446656 | Zbl 1144.05325
[33] P. Zumstein: Comparison of Spectral Methods Through the Adjacency Matrix and the Laplacian of a Graph: Diploma Thesis. ETH, Zürich (2005).
Affiliations: Emina Milovanović, University of Niš, Faculty of Electronic Engineering, Aleksandra Medvedeva 14, Niš 18106, Serbia, e-mail: ema@elfak.ni.ac.rs; Şerife Burcu Bozkurt Altındağ, Yenikent Kardelen Konutlari, Selçuklu, 42070 Konya, Turkey, e-mail: srf_burcu_bozkurt@hotmail.com; Marjan Matejić, Igor Milovanović, University of Niš, Faculty of Electronic Engineering, Aleksandra Medvedeva 14, Niš 18106, Serbia, e-mail: marjan.matejic@elfak.ni.ac.rs, igor@elfak.ni.ac.rs
