About DML-CZ | FAQ | Conditions of Use | Math Archives | Contact Us
  Previous |  Up |  Next

Article

Zhang, Minjie ; Li, Shuchao
Extremal properties of distance-based graph invariants for $k$-trees. (English). Mathematica Bohemica, vol. 143 (2018), issue 1, pp. 41-66
MSC: 34B16, 34C25 | MR 3778049 | Zbl 06861591 | DOI: 10.21136/MB.2017.0011-16
Keywords:
distance-based graph invariant; $k$-tree; simplicial vertex; sharp bound
Summary:
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).
References:
[1] Ali, P., Mukwembi, S., Munyira, S.: Degree distance and vertex-connectivity. Discrete Appl. Math. 161 (2013), 2802-2811. DOI 10.1016/j.dam.2013.06.033 | MR 3126647 | Zbl 1287.05075
[2] Alizadeh, Y., Iranmanesh, A., Došlić, T.: Additively weighted Harary index of some composite graphs. Discrete Math. 313 (2013), 26-34. DOI 10.1016/j.disc.2012.09.011 | MR 3016970 | Zbl 1254.05191
[3] Andrew, G. D., Gessel, I. M.: Counting unlabeled $k$-trees. J. Combin. Theory Ser. A 126 (2014), 177-193. DOI 10.1016/j.jcta.2014.05.002 | MR 3213312 | Zbl 1295.05078
[4] Azari, M., Iranmanesh, A.: Computing the eccentric-distance sum for graph operations. Discrete Appl. Math. 161 (2013), 2827-2840. DOI 10.1016/j.dam.2013.06.003 | MR 3126649 | Zbl 1287.05034
[5] Azari, M., Iranmanesh, A.: Harary index of some nano-structures. MATCH Commun. Math. Comput. Chem. 71 (2014), 373-382. MR 3184558 | Zbl 06704591
[6] Beineke, L. W., Pippert, R. E.: The number of labeled $k$-dimensional trees. J. Comb. Theory 6 (1969), 200-205. DOI 10.1016/S0021-9800(69)80120-1 | MR 0234868 | Zbl 0175.20904
[7] Bondy, J. A., Murty, U. S. R.: Graph Theory. Graduate Texts in Mathematics 244. Springer, Berlin (2008). MR 2368647 | Zbl 1134.05001
[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 10.1016/j.dam.2008.03.036 | MR 2467964 | Zbl 1168.05308
[9] Deng, H., Krishnakumari, B., Venkatakrishnan, Y. B., Balachandran, S.: Multiplicatively weighted Harary index of graphs. J. Comb. Optim. 30 (2015), 1125-1137. DOI 10.1007/s10878-013-9698-5 | MR 3411783 | Zbl 1327.05067
[10] Dobrynin, A. A., Entringer, R., Gutman, I.: Wiener index of trees: Theory and applications. Acta Appl. Math. 66 (2001), 211-249. DOI 10.1023/A:1010767517079 | MR 1843259 | Zbl 0982.05044
[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 10.1021/ci00021a008
[12] Estes, J., Wei, B.: Sharp bounds of the Zagreb indices of $k$-trees. J. Comb. Optim. 27 (2014), 271-291. DOI 10.1007/s10878-012-9515-6 | MR 3153716 | Zbl 1318.90070
[13] Geng, X., Li, S., Zhang, M.: Extremal values on the eccentric distance sum of trees. Discrete Appl. Math. 161 (2013), 2427-2439. DOI 10.1016/j.dam.2013.05.023 | MR 3101723 | Zbl 1285.05099
[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 10.1016/S0022-247X(02)00373-6 | MR 1941791 | Zbl 1005.92011
[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 1801517 | Zbl 1026.05101
[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 10.1016/0009-2614(72)85099-1
[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 3184562 | Zbl 06704595
[19] Hua, H., Wang, M.: On Harary index and traceable graphs. MATCH Commun. Math. Comput. Chem. 70 (2013), 297-300. MR 3136767 | Zbl 1299.05091
[20] Hua, H., Zhang, S.: On the reciprocal degree distance of graphs. Discrete Appl. Math. 160 (2012), 1152-1163. DOI 10.1016/j.dam.2011.11.032 | MR 2901134 | Zbl 1242.05060
[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 10.1007/BF01164642 | MR 1219579
[22] Klavžar, S., Gutman, I.: Wiener number of vertex-weighted graphs and a chemical application. Discrete Appl. Math. 80 (1997), 73-81. DOI 10.1016/S0166-218X(97)00070-X | MR 1489061 | Zbl 0889.05046
[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 10.1016/j.ejc.2013.04.008 | MR 3131875 | Zbl 1284.05118
[24] Li, X.-X., Fan, Y.-Z.: The connectivity and the Harary index of a graph. Discrete Appl. Math. 181 (2015), 167-173. DOI 10.1016/j.dam.2014.08.022 | MR 3284522 | Zbl 1304.05037
[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 10.1007/s10878-013-9649-1 | MR 3391560 | Zbl 1327.05092
[26] Li, S., Song, Y.: On the sum of all distances in bipartite graphs. Discrete Appl. Math. 169 (2014), 176-185. DOI 10.1016/j.dam.2013.12.010 | MR 3175067 | Zbl 1288.05072
[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 10.1016/j.dam.2016.01.027 | MR 3490432 | Zbl 1335.05059
[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 10.1016/j.jmaa.2015.05.032 | MR 3352002 | Zbl 1316.05071
[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 10.1016/j.dam.2013.11.019 | MR 3166121 | Zbl 1284.05063
[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 10.1016/j.dam.2015.01.042 | MR 3325557 | Zbl 1311.05054
[31] Mukungunugwa, V., Mukwembi, S.: On eccentric distance sum and minimum degree. Discrete Appl. Math. 175 (2014), 55-61. DOI 10.1016/j.dam.2014.05.019 | MR 3223906 | Zbl 1297.05076
[32] Mukwembi, S., Munyira, S.: Degree distance and minimum degree. Bull. Aust. Math. Soc. 87 (2013), 255-271. DOI 10.1017/S0004972712000354 | MR 3040710 | Zbl 1262.05040
[33] Panholzer, A., Seitz, G.: Ancestors and descendants in evolving $k$-tree models. Random Struct. Algorithms 44 (2014), 465-489. DOI 10.1002/rsa.20474 | MR 3214201 | Zbl 1296.05177
[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 10.1007/BF01164638 | MR 1219576
[35] Song, L., Staton, W., Wei, B.: Independence polynomials of $k$-tree related graphs. Discrete Appl. Math. 158 (2010), 943-950. DOI 10.1016/j.dam.2010.01.002 | MR 2602818 | Zbl 1219.05133
[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 10.1007/s10878-013-9645-5 | MR 3391557 | Zbl 1325.05071
[37] Tomescu, I., Kanwal, S.: Ordering connected graphs having small degree distances II. MATCH Commun. Math. Comput. Chem. 67 (2012), 425-437. MR 2951677 | Zbl 1289.05147
[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 10.1142/6518 | MR 2838951 | Zbl 1240.05202
[39] Wiener, H.: Structural determination of paraffin boiling points. J. Am. Chem. Soc. 69 (1947), 17-20. DOI 10.1021/ja01193a005
[40] Xu, K.: Trees with the seven smallest and eight greatest Harary indices. Discrete Appl. Math. 160 (2012), 321-331. DOI 10.1016/j.dam.2011.08.014 | MR 2862338 | Zbl 1237.05061
[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 10.1016/j.jmaa.2010.08.054 | MR 2735697 | Zbl 1282.05077
[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 10.1016/j.laa.2014.11.010 | MR 3284805 | Zbl 1304.05098
Partner of
EuDML logo