On the extremal total irregularity index of n-vertex trees with fixed maximum degree

Document Type : Original paper


Fast NUCES, Lahore, Pakistan.


In the extension of irregularity indices, Abdo et. al. {[H. Abdo, S. Brandt, D. Dimitrov, The total irregularity of a graph, Discrete Math. Theor. Comput. Sci. 16  (2014), 201--206]} defined the total irregularity of a graph $G = (V,E)$ as $irr_{t}(G)= \frac{1}{2} \sum_{u,v\in V(G)}  \big|d_u - d_v \big| $, where $d_u $ denotes the vertex degree of a vertex $u \in V(G)$. In this paper, we investigate the total irregularity of trees with bounded maximal degree $\Delta$ and state integer linear programming problem which gives standard information about extremal trees and it also calculates the index.


Main Subjects

[1] H. Abdo, S. Brandt, and D. Dimitrov, The total irregularity of a graph, Discrete Math. Theor. Comput. Sci. 16 (2014), no. 6, 201–206.
[2] H. Abdo and D. Dimitrov, The total irregularity of graphs under graph operations, Miskolc Math. Notes 15 (2014), no. 1, 3–17.
[3] M.O. Albertson, The irregularity of a graph, Ars Combin. 46 (1997), 219–225.
[4] A.R. Ashrafi, A. Ghalavand, and A. Ali, Molecular trees with the sixth, seventh and eighth minimal irregularity values, Discrete Math. Algorithms Appl. 11 (2019), no. 1, 1950002.
[5] F.K. Bell, A note on the irregularity of graphs, Linear Algebra Appl. 161 (1992), 45–54.
[6] L. Collatz and U. Sinogowitz, Spektren endlicher grafen, Abh. Math. Sem. Univ. Hamburg, vol. 21, Springer, 1957, pp. 63–77.
[7] R. Criado, J. Flores, A.G. del Amo, and M. Romance, Centralities of a network and its line graph: an analytical comparison by means of their irregularity, Int. J. Comput. Math. 91 (2014), no. 2, 304–314.
[8] D. Dimitrov and R. Skrekovski,  Comparing the irregularity and the total irregularity of graphs, Ars Math. Contemp. 9 (2014), no. 1, 45–50.
[9] E. Estrada, Quantifying network heterogeneity, Phys. Rev. E 82 (2010), no. 6, ID: 066102.
[10] E. Estrada, Randić index, irregularity and complex biomolecular networks, Acta Chim. Slov. 57 (2010), no. 3, 597–603.
[11] E. Estrada and D. Bonchev, Section 13.1. Chemical Graph Theory, Handbook of Graph Theory (2013), 1538–1558.
[12] J.L. Gross and J. Yellen, Graph Theory, CRC Press,Boca Raton, Florida, 2000.
[13] I. Gutman, P. Hansen, and H. Mélot, Variable neighborhood search for extremal graphs. 10. comparison of irregularity indices for chemical trees, J. Chem. Inf. Model. 45 (2005), no. 2, 222–230.
[14] F. Harary, Graph Theory, Addison-Wesley, 1969.
[15] T. Réti and A. Ali, On the variance-type graph irregularity measures, Commun. Comb. Optim. 5 (2020), no. 2, 169–178.
[16] T. Réti, R. Sharafdini, A. Drégelyi-Kiss, and H. Haghbin, Graph irregularity indices used as molecular descriptors in QSPR studies, MATCH Commun. Math. Comput. Chem. 79 (2018), no. 2, 509–524.
[17] L. You, J. Yang, and Z. You, The maximal total irregularity of unicyclic graphs, Ars Combin. 114 (2014), 153–160.
[18] L. You, J. Yang, Y. Zhu, and Z. You, The maximal total irregularity of bicyclic graphs, J. Appl. Math. 2014 (2014), ID: 785084.
[19] S. Yousaf, A.A. Bhatti, and A. Ali, A note on the modified Albertson index, Util. Math. (to appear).
[20] Y. Zhu, L. You, and J. Yang, The minimal total irregularity of some classes of graphs, Filomat 30 (2016), no. 5, 1203–1211.