Gutman index‎, ‎edge-Wiener index and edge-connectivity

Document Type : Research Paper

Authors

1 Department of Mathematics, University of Zimbabwe, P. O. Box MP 167, Mount Pleasant, Harare, Zimbabwe

2 School of Mathematics, University of the Witwatersrand, Private Bag 3, Wits 2050, South Africa

3 Department of Mathematics and Applied Mathematics, University of the Free State, P. O. Box 339, Bloemfontein, 9300, South Africa

Abstract

‎We study the Gutman index ${\rm Gut}(G)$ and the edge-Wiener index $W_e (G)$ of connected graphs $G$ of given order $n$ and edge-connectivity $\lambda$‎. ‎We show that the bound ${\rm Gut}(G) \le \frac{2^4 \cdot 3}{5^5 (\lambda+1)} n^5‎ + ‎O(n^4)$ is asymptotically tight for $\lambda \ge 8$‎. ‎We improve this result considerably for $\lambda \le 7$ by presenting asymptotically tight upper bounds on ${\rm Gut}(G)$ and $W_e (G)$ for $2 \le \lambda \le 7$‎.

Keywords

Main Subjects

References

[1] P. Ali, J. P. Mazorodze, S. Mukwembi and T. Vetrı́k, On size, order, diameter and edge-connectivity of graphs, Acta
Math. Hungar., 152 (2017) 11–24.
[2] V. Andova, D. Dimitrov, J. Fink and R. Škrekovski, Bounds on Gutman index, MATCH Commun. Math. Comput.
Chem., 67 (2012) 515–524.
[3] M. Azari and A. Iranmanesh, Computation of the edge Wiener indices of the sum of graphs, Ars Combin., 100
(2011) 113–128.
[4] S. Chen, Cacti with the smallest, second smallest, and third smallest Gutman index, J. Comb. Optim., 31 (2016)
327–332.
[5] A. Chen, X. Xiong and 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.
[6] P. Dankelmann, I. Gutman, S. Mukwembi and H. C. Swart, The edge-Wiener index of a graph, Discrete Math., 309
(2009) 3452–3457.
[7] K. C. Das, G. Su and L. Xiong, Relation between degree distance and Gutman index of graphs, MATCH Commun.
Math. Comput. Chem., 76 (2016) 221–232.
[8] L. Feng, The Gutman index of unicyclic graphs, Discrete Math. Algorithms Appl., 4 (2012) 669–708.
[9] L. Feng and W. Liu, The maximal Gutman index of bicyclic graphs, MATCH Commun. Math. Comput. Chem., 66
(2011) 699–708.
[10] I. Gutman, Selected properties of the Schultz molecular topological index, J. Chem. Inf. Comput. Sci., 34 (1994)
1087–1089.
[11] A. Iranmanesh, I. Gutman, O. Khormali and A. Mahmiani, The edge versions of the Wiener index, MATCH
Commun. Math. Comput. Chem., 61 (2009) 663–672.
[12] M. H. Khalifeh, H. Yousefi-Azari, A. R. Ashrafi and S. G. Wagner, Some new results on distance-based graph
invariants, European J. Combin., 30 (2009) 1149–1163.
[13] M. Knor, P. Potočnik and R. Škrekovski, Relationship between the edge-Wiener index and the Gutman index of a
graph, Discrete Appl. Math., 167 (2014) 197–201.
[14] M. Knor, R. Škrekovski and A. Tepeh, An inequality between the edge-Wiener index and the Wiener index of a
graph, Appl. Math. Comput., 269 (2015) 714–721.
[15] J. P. Mazorodze, S. Mukwembi and T. Vetrı́k, On the Gutman index and minimum degree, Discrete Appl. Math.,
173 (2014) 77–82.
[16] J. P. Mazorodze, S. Mukwembi and T. Vetrı́k, The Gutman index and the edge-Wiener index of graphs with given
vertex-connectivity, Discuss. Math. Graph Theory, 36 (2016) 867–876.
[17] S. Mukwembi, On the upper bound of Gutman index of graphs, MATCH Commun. Math. Comput. Chem., 68
(2012) 343–348.
[18] M. J. Nadjafi-Arani, H. Khodashenas and A. R. Ashrafi, Relationship between edge Szeged and edge Wiener indices
of graphs, Glas. Mat. Ser. III, 47 (2012) 21–29.
Transactions on Combinatorics
Volume 9, Issue 4 - Serial Number 4
December 2020
Pages 231-242

Files

Cited by

History

  • Receive Date: 23 July 2020
  • Revise Date: 10 August 2020
  • Accept Date: 10 August 2020
  • Published Online: 01 December 2020

Share

How to cite

Statistics