On the Distance Spectral Radius of Trees with Given Degree Sequence

Dadedzi, Kenneth ; Misanantenaina, Valisoa Razanajatovo ; Wagner, Stephan

Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 495-524.

Résumé

We consider the problem of maximizing the distance spectral radius and a slight generalization thereof among all trees with some prescribed degree sequence. We prove in particular that the maximum of the distance spectral radius has to be attained by a caterpillar for any given degree sequence. The same holds true for the terminal distance matrix. Moreover, we consider a generalized version of the reverse distance matrix and also study its spectral radius for trees with given degree sequence. We prove that the spectral radius is always maximized by a greedy tree. This implies several corollaries, among them a “reversed” version of a conjecture of Stevanović and Ilić. Our results parallel similar theorems for the Wiener index and other invariants.

Détail

Keywords: distance matrix, spectral radius, tree, degree sequence

Bibliographie

[1] A.T. Balaban, D. Mills, O. Ivanciuc and S.C. Basak, Reverse Wiener indices, Croat. Chem. Acta 73 (2000) 923–941.

[2] R.B. Bapat, Determinant of the distance matrix of a tree with matrix weights, Linear Algebra Appl. 416 (2006) 2–7. doi:10.1016/j.laa.2005.02.022

[3] R.B. Bapat, Graphs and Matrices (Springer, 2010). doi:10.1007/978-1-84882-981-7

[4] R.B. Bapat, S.J. Kirkland and M. Neumann, On distance matrices and Laplacians, Linear Algebra Appl. 401 (2005) 193–209. doi:10.1016/j.laa.2004.05.011

[5] T. Bıyıkoğlu and J. Leydold, Graphs with given degree sequence and maximal spectral radius, Electron. J. Combin. 15 (2008) #R119.

[6] S.S. Bose, M. Nath and S. Paul, Distance spectral radius of graphs with r pendent vertices, Linear Algebra Appl. 435 (2011) 2828–2836. doi:10.1016/j.laa.2011.04.041

[7] S.S. Bose, M. Nath and S. Paul, On the maximal distance spectral radius of graphs without a pendent vertex, Linear Algebra Appl. 438 (2013) 4260–4278. doi:10.1016/j.laa.2013.01.019

[8] S.S. Bose, M. Nath and D. Sarma, Maximal distance spectral radius of trees, Discrete Math. Algorithms Appl. 11 (2019) 1950025. doi:10.1142/S1793830919500253

[9] E. Çela, N.S. Schmuck, S. Wimer and G.J. Woeginger, The Wiener maximum quadratic assignment problem, Discrete Optim. 8 (2011) 411–416. doi:10.1016/j.disopt.2011.02.002

[10] K.L. Collins, Distance Matrices of Trees (Ph.D. Thesis, Massachusetts Institute of Technology, 1986).

[11] M. Fischermann, A. Homann, D. Rautenbach, L. Székely and L. Volkmann, Wiener index versus maximum degree in trees, Discrete Appl. Math. 122 (2002) 127–137. doi:10.1016/S0166-218X(01)00357-2

[12] M. Goubko, On minimum terminal distance spectral radius of trees with given degree sequence, (2015). arXiv:1507.01733

[13] R.L. Graham and H.O. Pollak, On the addressing problem for loop switching, Bell System Tech. J. 50 (1971) 2495–2519. doi:10.1002/j.1538-7305.1971.tb02618.x

[14] G.H. Hardy, J.E. Littlewood and G. Pólya, Inequalities (Cambridge University Press, 1952).

[15] A. Heydari, On extremal trees with respect to their terminal distance spectral radius, Australas. J. Combin. 69 (2017) 159–168.

[16] A. Ilić, Distance spectral radius of trees with given matching number, Discrete Appl. Math. 158 (2010) 1799–1806. doi:10.1016/j.dam.2010.06.018

[17] G. Indulal, Sharp bounds on the distance spectral radius and the distance energy of graphs, Linear Algebra Appl. 430 (2009) 106–113. doi:10.1016/j.laa.2008.07.005

[18] H. Lin and B. Zhou, The distance spectral radius of graphs with given number of odd vertices, Electron. J. Linear Algebra 31 (2016) 286–305. doi:10.13001/1081-3810.2877

[19] H. Lin and B. Zhou, The distance spectral radius of trees, Linear Multilinear Algebra 67 (2018) 370–390. doi:10.1080/03081087.2017.1418830

[20] W. Lin, Y. Zhang, Q. Chen, J. Chen, C. Ma and J. Chen, Ordering trees by their distance spectral radii, Discrete Appl. Math. 203 (2016) 106–110. doi:10.1016/j.dam.2015.09.009

[21] Z. Luo and B. Zhou, On distance spectral radius of trees and fixed maximum degree, Filomat 29 (2015) 2021–2026. doi:10.2298/FIL1509021L

[22] M. Nath and S. Paul, On the distance spectral radius of trees, Linear Multilinear Algebra 61 (2013) 847–855. doi:10.1080/03081087.2012.711324

[23] W. Ning, L. Ouyang and M. Lu, Distance spectral radius of trees with fixed number of pendent vertices, Linear Algebra Appl. 439 (2013) 2240–2249. doi:10.1016/j.laa.2013.06.030

[24] N.S. Schmuck, S.G. Wagner and H. Wang, Greedy trees, caterpillars, and Wiener-type graph invariants, MATCH Commun. Math. Comput. Chem. 68 (2012) 273–292.

[25] D. Stevanović and A. Ilić, Distance spectral radius of trees with fixed maximum degree, Electron. J. Linear Algebra 20 (2010) 168–179. doi:10.13001/1081-3810.1366

[26] L.A. Székely, H. Wang and T. Wu, The sum of the distances between the leaves of a tree and the semi-regular property, Discrete Math. 311 (2011) 1197–1203. doi:10.1016/j.disc.2010.06.005

[27] H. Wang, The extremal values of the Wiener index of a tree with given degree sequence, Discrete Appl. Math. 156 (2008) 2647–2654. doi:10.1016/j.dam.2007.11.005

[28] Y. Wang, R. Xing, B. Zhou and F. Dong, A note on distance spectral radius of trees, Spec. Matrices 5 (2017) 296–300. doi:10.1515/spma-2017-0021

[29] Y. Wang and B. Zhou, On distance spectral radius of graphs, Linear Algebra Appl. 438 (2013) 3490–3503. doi:10.1016/j.laa.2012.12.024

[30] R. Xing, B. Zhou and F. Dong, The effect of a graft transformation on distance spectral radius, Linear Algebra Appl. 457 (2014) 261–275. doi:10.1016/j.laa.2014.05.024

[31] G. Yu, S. Guo and M. Zhai, Distance spectral radius of a tree with given diameter, Ars Combin. 134 (2017) 351–362.

[32] X.-D. Zhang, The Laplacian spectral radii of trees with given degree sequences, Discrete Math. 308 (2008) 3143–3150. doi:10.1016/j.disc.2007.06.017

[33] X.-D. Zhang, Q.-Y. Xiang, L.-Q. Xu and R.-Y. Pan, The Wiener index of trees with given degree sequences, MATCH Commun. Math. Comput. Chem. 60 (2008) 623–644.