Extremal properties of distance-based graph invariants for -trees

Minjie Zhang; Shuchao Li

Mathematica Bohemica (2018)

  • Volume: 143, Issue: 1, page 41-66
  • ISSN: 0862-7959

Abstract

top
Sharp bounds on some distance-based graph invariants of -vertex -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 -trees with 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).

How to cite

top

Zhang, Minjie, and Li, Shuchao. "Extremal properties of distance-based graph invariants for $k$-trees." Mathematica Bohemica 143.1 (2018): 41-66. <http://eudml.org/doc/294875>.

@article{Zhang2018,
abstract = {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).},
author = {Zhang, Minjie, Li, Shuchao},
journal = {Mathematica Bohemica},
keywords = {distance-based graph invariant; $k$-tree; simplicial vertex; sharp bound},
language = {eng},
number = {1},
pages = {41-66},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Extremal properties of distance-based graph invariants for $k$-trees},
url = {http://eudml.org/doc/294875},
volume = {143},
year = {2018},
}

TY - JOUR
AU - Zhang, Minjie
AU - Li, Shuchao
TI - Extremal properties of distance-based graph invariants for $k$-trees
JO - Mathematica Bohemica
PY - 2018
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 143
IS - 1
SP - 41
EP - 66
AB - 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).
LA - eng
KW - distance-based graph invariant; $k$-tree; simplicial vertex; sharp bound
UR - http://eudml.org/doc/294875
ER -

References

top
  1. Ali, P., Mukwembi, S., Munyira, S., 10.1016/j.dam.2013.06.033, Discrete Appl. Math. 161 (2013), 2802-2811. (2013) Zbl1287.05075MR3126647DOI10.1016/j.dam.2013.06.033
  2. Alizadeh, Y., Iranmanesh, A., Došlić, T., 10.1016/j.disc.2012.09.011, Discrete Math. 313 (2013), 26-34. (2013) Zbl1254.05191MR3016970DOI10.1016/j.disc.2012.09.011
  3. Andrew, G. D., Gessel, I. M., 10.1016/j.jcta.2014.05.002, J. Combin. Theory Ser. A 126 (2014), 177-193. (2014) Zbl1295.05078MR3213312DOI10.1016/j.jcta.2014.05.002
  4. Azari, M., Iranmanesh, A., 10.1016/j.dam.2013.06.003, Discrete Appl. Math. 161 (2013), 2827-2840. (2013) Zbl1287.05034MR3126649DOI10.1016/j.dam.2013.06.003
  5. Azari, M., Iranmanesh, A., Harary index of some nano-structures, MATCH Commun. Math. Comput. Chem. 71 (2014), 373-382. (2014) Zbl06704591MR3184558
  6. Beineke, L. W., Pippert, R. E., 10.1016/S0021-9800(69)80120-1, J. Comb. Theory 6 (1969), 200-205. (1969) Zbl0175.20904MR0234868DOI10.1016/S0021-9800(69)80120-1
  7. Bondy, J. A., Murty, U. S. R., Graph Theory, Graduate Texts in Mathematics 244. Springer, Berlin (2008). (2008) Zbl1134.05001MR2368647
  8. Bucicovschi, O., Cioabă, S. M., 10.1016/j.dam.2008.03.036, Discrete Appl. Math. 156 (2008), 3518-3521. (2008) Zbl1168.05308MR2467964DOI10.1016/j.dam.2008.03.036
  9. Deng, H., Krishnakumari, B., Venkatakrishnan, Y. B., Balachandran, S., 10.1007/s10878-013-9698-5, J. Comb. Optim. 30 (2015), 1125-1137. (2015) Zbl1327.05067MR3411783DOI10.1007/s10878-013-9698-5
  10. Dobrynin, A. A., Entringer, R., Gutman, I., 10.1023/A:1010767517079, Acta Appl. Math. 66 (2001), 211-249. (2001) Zbl0982.05044MR1843259DOI10.1023/A:1010767517079
  11. Dobrynin, A. A., Kochetova, A. A., 10.1021/ci00021a008, J. Chem. Inf. Comput. Sci. 34 (1994), 1082-1086. (1994) DOI10.1021/ci00021a008
  12. Estes, J., Wei, B., 10.1007/s10878-012-9515-6, J. Comb. Optim. 27 (2014), 271-291. (2014) Zbl1318.90070MR3153716DOI10.1007/s10878-012-9515-6
  13. Geng, X., Li, S., Zhang, M., 10.1016/j.dam.2013.05.023, Discrete Appl. Math. 161 (2013), 2427-2439. (2013) Zbl1285.05099MR3101723DOI10.1016/j.dam.2013.05.023
  14. Gupta, S., Singh, M., Madan, A. K., 10.1016/S0022-247X(02)00373-6, J. Math. Anal. Appl. 275 (2002), 386-401. (2002) Zbl1005.92011MR1941791DOI10.1016/S0022-247X(02)00373-6
  15. Gutman, I., A property of the Wiener number and its modifications, Indian J. Chem. A 36 (1997), 128-132. (1997) 
  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. (2000) Zbl1026.05101MR1801517
  17. I, I. Gutman, Trinajstić, N., 10.1016/0009-2614(72)85099-1, Chem. Phys. Lett. 17 (1972), 535-538. (1972) DOI10.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. (2014) Zbl06704595MR3184562
  19. Hua, H., Wang, M., On Harary index and traceable graphs, MATCH Commun. Math. Comput. Chem. 70 (2013), 297-300. (2013) Zbl1299.05091MR3136767
  20. Hua, H., Zhang, S., 10.1016/j.dam.2011.11.032, Discrete Appl. Math. 160 (2012), 1152-1163. (2012) Zbl1242.05060MR2901134DOI10.1016/j.dam.2011.11.032
  21. Ivanciuc, O., Balaban, T. S., Balaban, A. T., 10.1007/BF01164642, Applied Graph Theory and Discrete Mathematics in Chemistry. Proc. Symp., Saskatoon, 1991. Baltzer Science Publishers BV, Bussum, J. Math. Chem. (1993) P. G. Mezey et al. 309-318. MR1219579DOI10.1007/BF01164642
  22. Klavžar, S., Gutman, I., 10.1016/S0166-218X(97)00070-X, Discrete Appl. Math. 80 (1997), 73-81. (1997) Zbl0889.05046MR1489061DOI10.1016/S0166-218X(97)00070-X
  23. Klavžar, S., Nadjafi-Arani, M. J., 10.1016/j.ejc.2013.04.008, European J. Combin. 36 (2014), 71-76. (2014) Zbl1284.05118MR3131875DOI10.1016/j.ejc.2013.04.008
  24. Li, X.-X., Fan, Y.-Z., 10.1016/j.dam.2014.08.022, Discrete Appl. Math. 181 (2015), 167-173. (2015) Zbl1304.05037MR3284522DOI10.1016/j.dam.2014.08.022
  25. Li, S., Meng, X., 10.1007/s10878-013-9649-1, J. Comb. Optim. 30 (2015), 468-488. (2015) Zbl1327.05092MR3391560DOI10.1007/s10878-013-9649-1
  26. Li, S., Song, Y., 10.1016/j.dam.2013.12.010, Discrete Appl. Math. 169 (2014), 176-185. (2014) Zbl1288.05072MR3175067DOI10.1016/j.dam.2013.12.010
  27. Li, S., Wu, Y., 10.1016/j.dam.2016.01.027, Discrete Appl. Math. 206 (2016), 90-99. (2016) Zbl1335.05059MR3490432DOI10.1016/j.dam.2016.01.027
  28. Li, S., Wu, Y., Sun, L., 10.1016/j.jmaa.2015.05.032, J. Math. Anal. Appl. 430 (2015), 1149-1162. (2015) Zbl1316.05071MR3352002DOI10.1016/j.jmaa.2015.05.032
  29. Maxová, J., Dubcová, M., Pavlíková, P., Turzík, D., 10.1016/j.dam.2013.11.019, Discrete Appl. Math. 167 (2014), 222-227. (2014) Zbl1284.05063MR3166121DOI10.1016/j.dam.2013.11.019
  30. Miao, L., Cao, Q., Cui, N., Pang, S., 10.1016/j.dam.2015.01.042, Discrete Appl. Math. 186 (2015), 199-206. (2015) Zbl1311.05054MR3325557DOI10.1016/j.dam.2015.01.042
  31. Mukungunugwa, V., Mukwembi, S., 10.1016/j.dam.2014.05.019, Discrete Appl. Math. 175 (2014), 55-61. (2014) Zbl1297.05076MR3223906DOI10.1016/j.dam.2014.05.019
  32. Mukwembi, S., Munyira, S., 10.1017/S0004972712000354, Bull. Aust. Math. Soc. 87 (2013), 255-271. (2013) Zbl1262.05040MR3040710DOI10.1017/S0004972712000354
  33. Panholzer, A., Seitz, G., 10.1002/rsa.20474, Random Struct. Algorithms 44 (2014), 465-489. (2014) Zbl1296.05177MR3214201DOI10.1002/rsa.20474
  34. Plavšić, D., Nikolić, S., Trinajstić, N., Mihalić, Z., 10.1007/BF01164638, Applied Graph Theory and Discrete Mathematics in Chemistry. Proc. Symp., Saskatoon, 1991. Baltzer Science Publishers BV, Bussum, J. Math. Chem. (1993) P. G. Mezey et al. 235-250. MR1219576DOI10.1007/BF01164638
  35. Song, L., Staton, W., Wei, B., 10.1016/j.dam.2010.01.002, Discrete Appl. Math. 158 (2010), 943-950. (2010) Zbl1219.05133MR2602818DOI10.1016/j.dam.2010.01.002
  36. Su, G., Xiong, L., Su, X., Chen, X., 10.1007/s10878-013-9645-5, J. Comb. Optim. 30 (2015), 435-446. (2015) Zbl1325.05071MR3391557DOI10.1007/s10878-013-9645-5
  37. Tomescu, I., Kanwal, S., Ordering connected graphs having small degree distances II, MATCH Commun. Math. Comput. Chem. 67 (2012), 425-437. (2012) Zbl1289.05147MR2951677
  38. Wang, X., Zhai, M., Shu, J., 10.1142/6518, Appl. Math., Ser. A 26 (2011), 209-214 Chinese. English summary. (2011) Zbl1240.05202MR2838951DOI10.1142/6518
  39. Wiener, H., 10.1021/ja01193a005, J. Am. Chem. Soc. 69 (1947), 17-20. (1947) DOI10.1021/ja01193a005
  40. Xu, K., 10.1016/j.dam.2011.08.014, Discrete Appl. Math. 160 (2012), 321-331. (2012) Zbl1237.05061MR2862338DOI10.1016/j.dam.2011.08.014
  41. Yu, G., Feng, L., Ilić, A., 10.1016/j.jmaa.2010.08.054, J. Math. Anal. Appl. 375 (2011), 99-107. (2011) Zbl1282.05077MR2735697DOI10.1016/j.jmaa.2010.08.054
  42. Zhang, M., Li, S., 10.1016/j.laa.2014.11.010, Linear Algebra Appl. 467 (2015), 136-148 corrigendum ibid. 485 527-530 2015. (2015) Zbl1304.05098MR3284805DOI10.1016/j.laa.2014.11.010

NotesEmbed ?

top

You must be logged in to post comments.