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