Extremal properties of distance-based graph invariants for $k$-trees

Zhang, Minjie ; Li, Shuchao

Mathematica Bohemica, Tome 143 (2018) no. 1, pp. 41-66

Abstract (VO)

Sharp bounds on some distance-based graph invariants of $n$-vertex $k$-trees are established in a unified approach, which may be viewed as the weighted Wiener index or weighted Harary index. The main techniques used in this paper are graph transformations and mathematical induction. Our results demonstrate that among $k$-trees with $n$ vertices the extremal graphs with the maximal and the second maximal reciprocal sum-degree distance are coincident with graphs having the maximal and the second maximal reciprocal product-degree distance (and similarly, the extremal graphs with the minimal and the second minimal degree distance are coincident with graphs having the minimal and the second minimal eccentricity distance sum).

Détail

DOI : 10.21136/MB.2017.0011-16

Classification : 34B16, 34C25
Keywords: distance-based graph invariant; $k$-tree; simplicial vertex; sharp bound

Bibliographie

[1] Ali, P., Mukwembi, S., Munyira, S.: Degree distance and vertex-connectivity. Discrete Appl. Math. 161 (2013), 2802-2811. | DOI | MR | JFM

[2] Alizadeh, Y., Iranmanesh, A., Došlić, T.: Additively weighted Harary index of some composite graphs. Discrete Math. 313 (2013), 26-34. | DOI | MR | JFM

[3] Andrew, G. D., Gessel, I. M.: Counting unlabeled $k$-trees. J. Combin. Theory Ser. A 126 (2014), 177-193. | DOI | MR | JFM

[4] Azari, M., Iranmanesh, A.: Computing the eccentric-distance sum for graph operations. Discrete Appl. Math. 161 (2013), 2827-2840. | DOI | MR | JFM

[5] Azari, M., Iranmanesh, A.: Harary index of some nano-structures. MATCH Commun. Math. Comput. Chem. 71 (2014), 373-382. | MR | JFM

[6] Beineke, L. W., Pippert, R. E.: The number of labeled $k$-dimensional trees. J. Comb. Theory 6 (1969), 200-205. | DOI | MR | JFM

[7] Bondy, J. A., Murty, U. S. R.: Graph Theory. Graduate Texts in Mathematics 244. Springer, Berlin (2008). | MR | JFM

[8] Bucicovschi, O., Cioabă, S. M.: The minimum degree distance of graphs of given order and size. Discrete Appl. Math. 156 (2008), 3518-3521. | DOI | MR | JFM

[9] Deng, H., Krishnakumari, B., Venkatakrishnan, Y. B., Balachandran, S.: Multiplicatively weighted Harary index of graphs. J. Comb. Optim. 30 (2015), 1125-1137. | DOI | MR | JFM

[10] Dobrynin, A. A., Entringer, R., Gutman, I.: Wiener index of trees: Theory and applications. Acta Appl. Math. 66 (2001), 211-249. | DOI | MR | JFM

[11] Dobrynin, A. A., Kochetova, A. A.: Degree distance of a graph: A degree analogue of the Wiener index. J. Chem. Inf. Comput. Sci. 34 (1994), 1082-1086. | DOI

[12] Estes, J., Wei, B.: Sharp bounds of the Zagreb indices of $k$-trees. J. Comb. Optim. 27 (2014), 271-291. | DOI | MR | JFM

[13] Geng, X., Li, S., Zhang, M.: Extremal values on the eccentric distance sum of trees. Discrete Appl. Math. 161 (2013), 2427-2439. | DOI | MR | JFM

[14] Gupta, S., Singh, M., Madan, A. K.: Eccentric distance sum: A novel graph invariant for predicting biological and physical properties. J. Math. Anal. Appl. 275 (2002), 386-401. | DOI | MR | JFM

[15] Gutman, I.: A property of the Wiener number and its modifications. Indian J. Chem. A 36 (1997), 128-132.

[16] Gutman, I., Rada, J., Araujo, O.: The Wiener index of starlike trees and a related partial order. MATCH Commun. Math. Comput. Chem. 42 (2000), 145-154. | MR | JFM

[17] I, I. Gutman, Trinajstić, N.: Graph theory and molecular orbitals: Total $\phi$-electron energy of alternant hydrocarbons. Chem. Phys. Lett. 17 (1972), 535-538. | DOI

[18] Hemmasi, M., Iranmanesh, A., Tehranian, A.: Computing eccentric distance sum for an infinite family of fullerenes. MATCH Commun. Math. Comput. Chem. 71 (2014), 417-424. | MR | JFM

[19] Hua, H., Wang, M.: On Harary index and traceable graphs. MATCH Commun. Math. Comput. Chem. 70 (2013), 297-300. | MR | JFM

[20] Hua, H., Zhang, S.: On the reciprocal degree distance of graphs. Discrete Appl. Math. 160 (2012), 1152-1163. | DOI | MR | JFM

[21] Ivanciuc, O., Balaban, T. S., Balaban, A. T.: Design of topological indices IV: Reciprocal distance matrix, related local vertex invariants and topological indices. Applied Graph Theory and Discrete Mathematics in Chemistry. Proc. Symp., Saskatoon, 1991. Baltzer Science Publishers BV, Bussum, J. Math. Chem. {\it 12} (1993) P. G. Mezey et al. 309-318. | DOI | MR

[22] Klavžar, S., Gutman, I.: Wiener number of vertex-weighted graphs and a chemical application. Discrete Appl. Math. 80 (1997), 73-81. | DOI | MR | JFM

[23] Klavžar, S., Nadjafi-Arani, M. J.: Wiener index in weighted graphs via unification of $\Theta^*$-classes. European J. Combin. 36 (2014), 71-76. | DOI | MR | JFM

[24] Li, X.-X., Fan, Y.-Z.: The connectivity and the Harary index of a graph. Discrete Appl. Math. 181 (2015), 167-173. | DOI | MR | JFM

[25] Li, S., Meng, X.: Four edge-grafting theorems on the reciprocal degree distance of graphs and their applications. J. Comb. Optim. 30 (2015), 468-488. | DOI | MR | JFM

[26] Li, S., Song, Y.: On the sum of all distances in bipartite graphs. Discrete Appl. Math. 169 (2014), 176-185. | DOI | MR | JFM

[27] Li, S., Wu, Y.: On the extreme eccentric distance sum of graphs with some given parameters. Discrete Appl. Math. 206 (2016), 90-99. | DOI | MR | JFM

[28] Li, S., Wu, Y., Sun, L.: On the minimum eccentric distance sum of bipartite graphs with some given parameters. J. Math. Anal. Appl. 430 (2015), 1149-1162. | DOI | MR | JFM

[29] Maxová, J., Dubcová, M., Pavlíková, P., Turzík, D.: Which $k$-trees are cover-incomparability graphs?. Discrete Appl. Math. 167 (2014), 222-227. | DOI | MR | JFM

[30] Miao, L., Cao, Q., Cui, N., Pang, S.: On the extremal values of the eccentric distance sum of trees. Discrete Appl. Math. 186 (2015), 199-206. | DOI | MR | JFM

[31] Mukungunugwa, V., Mukwembi, S.: On eccentric distance sum and minimum degree. Discrete Appl. Math. 175 (2014), 55-61. | DOI | MR | JFM

[32] Mukwembi, S., Munyira, S.: Degree distance and minimum degree. Bull. Aust. Math. Soc. 87 (2013), 255-271. | DOI | MR | JFM

[33] Panholzer, A., Seitz, G.: Ancestors and descendants in evolving $k$-tree models. Random Struct. Algorithms 44 (2014), 465-489. | DOI | MR | JFM

[34] Plavšić, D., Nikolić, S., Trinajstić, N., Mihalić, Z.: On the Harary index for the characterization of chemical graphs. Applied Graph Theory and Discrete Mathematics in Chemistry. Proc. Symp., Saskatoon, 1991. Baltzer Science Publishers BV, Bussum, J. Math. Chem. {\it 12} (1993) P. G. Mezey et al. 235-250. | DOI | MR

[35] Song, L., Staton, W., Wei, B.: Independence polynomials of $k$-tree related graphs. Discrete Appl. Math. 158 (2010), 943-950. | DOI | MR | JFM

[36] Su, G., Xiong, L., Su, X., Chen, X.: Some results on the reciprocal sum-degree distance of graphs. J. Comb. Optim. 30 (2015), 435-446. | DOI | MR | JFM

[37] Tomescu, I., Kanwal, S.: Ordering connected graphs having small degree distances II. MATCH Commun. Math. Comput. Chem. 67 (2012), 425-437. | MR | JFM

[38] Wang, X., Zhai, M., Shu, J.: Upper bounds on the spectral radius of $k$-trees. Appl. Math., Ser. A 26 (2011), 209-214 Chinese. English summary. | DOI | MR | JFM

[39] Wiener, H.: Structural determination of paraffin boiling points. J. Am. Chem. Soc. 69 (1947), 17-20. | DOI

[40] Xu, K.: Trees with the seven smallest and eight greatest Harary indices. Discrete Appl. Math. 160 (2012), 321-331. | DOI | MR | JFM

[41] Yu, G., Feng, L., Ilić, A.: On the eccentric distance sum of trees and unicyclic graphs. J. Math. Anal. Appl. 375 (2011), 99-107. | DOI | MR | JFM

[42] Zhang, M., Li, S.: On the signless Laplacian spectra of $k$-trees. Linear Algebra Appl. 467 (2015), 136-148 corrigendum ibid. 485 527-530 2015. | DOI | MR | JFM