Trees with the greatest Wiener and edge-Wiener index

Document Type: Research Paper

Author

Department of Pure Mathematics, Faculty of Mathematical Sciences, University of Kashan, Kashan 87317-53153, I R Iran

Abstract

The Wiener index W and the edge-Wiener index W_e of G are defined as the sum of distances between all pairs of vertices in G and the sum of distances between all pairs of edges in G, respectively. In this paper, we identify the four trees, with the first through fourth greatest Wiener and edge-Wiener index among all trees of order n ≥ 10.

Keywords

Main Subjects


 

  1. Y. Alizadeh, A. Iranmanesh, T. Doŝlić, M. Azari, The edge Wiener index of suspensions, bottlenecks, and thorny graphs, Glas. Mat. Ser. III 49 (69) (2014) 1−12.
  2. M. Azari, A. Iranmanesh, A. Tehranian, A method for calculating an edge version of the Wiener number of a graph operation, Util. Math. 87 (2012) 151−164.
  3. F. Buckley, Mean distance in line graphs, Congr. Numer. 32 (1981) 153−162.
  4. A. Chen, X. Xiong, F. Lin, Explicit relation between the Wiener index and the edge-Wiener index of the catacondensed hexagonal systems, Appl. Math. Comput. 273 (2016) 1100−1106.
  5. P. Dankelmann, I. Gutman, S. Mukwembi, H. C. Swart, The edge–Wiener index of a graph, Discrete Math. 309 (2009) 3452−3457.
  6. Y. Dou, H. Bian, H. Gao, H. Yu, The polyphenyl chains with extremal edge–Wiener indices, MATCH Commun. Math. Comput. Chem. 64 (2010) 757−766.
  7. J. Devillers, A.T. Balaban, Topological Indices and Related Descriptors in QSAR and QSPR, Gordon and Breach Science Publishers, 1999.
  8. H.-Y. Deng, The trees on  vertices with the first to seventeenth greatest Wiener indices are chemical trees, MATCH Commun. Math. Comput. Chem. 57 (2007) 393−402.
  9. A. Iranmanesh, M. Azari, Edge–Wiener descriptors in chemical graph theory: a survey, Curr. Org. Chem. 19 (2015) 219−239.
  10.  A. Iranmanesh, I. Gutman, O. Khormali, A. Mahmiani, The edge versions of Wiener index, MATCH Commun. Math. Comput. Chem. 61 (2009) 663−672.
  11.  M. Karelson, Molecular Descriptors in QSAR/QSPR, Wiley, New York, 2000.
  12. M. Knor, P. Potočnik, R. Škrekovski, Relationship between the edge-Wiener index and the Gutman index of a graph, Discrete Appl. Math. 167 (2014) 197−201.
  13. M. H. Khalifeh, H. Yousefi Azari, A. R. Ashrafi, S. G. Wagner, Some new results on distance–based graph invariants, European J. Comb. 30 (2009) 1149−1163.
  14. A. Kelenc, S. Klavžar, N. Tratnik, The Edge–Wiener index of benzenoid systems in linear time, MATCH Commun. Math. Comput. Chem. 74 (2015) 521−532.
  15. M. Liu, B. Liu, Q. Li, Erratum to: The trees on  vertices with the first to seventeenth greatest Wiener indices are chemical trees, MATCH Commun. Math. Comput. Chem. 64 (2010) 743−756.
  16. M. J. Nadjafi–Arani, H. Khodashenas, A. R. Ashrafi, Relationship between edge Szeged and edge Wiener indices of graphs, Glas. Mat. Ser. III 47 (67) (2012) 21−29.
  17. N. Tratnik, P. Žigert Pleteršek, Relationship between the Hosoya polynomial and the edge-Hosoya polynomial of trees, MATCH Commun. Math. Comput. Chem. 78 (2017) 181−187.
  18. H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc.
    69 (1947) 17−20.
  19. H. Yousefi–Azari, M. H. Khalifeh, A. R. Ashrafi, Calculating the edge Wiener and edge Szeged indices of graphs, J. Comput. Appl. Math. 235 (2011) 4866−4870.