Glasnik Matematicki, Vol. 47, No. 1 (2012), 21-29.

RELATIONSHIP BETWEEN EDGE SZEGED AND EDGE WIENER INDICES OF GRAPHS

Mohammad Javad Nadjafi-Arani, Hasan Khodashenas and Ali Reza Ashrafi

Department of Mathematics, Statistics and Computer Science, Faculty of Science, University of Kashan, Kashan 87317-51167, I. R. Iran
e-mail: mjnajafiarani@gmail.com

Department of Mathematics, Statistics and Computer Science, Faculty of Science, University of Kashan, Kashan 87317-51167, I. R. Iran

Department of Mathematics, Statistics and Computer Science, Faculty of Science, University of Kashan, Kashan 87317-51167, I. R. Iran
and
School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box: 19395-5746, Tehran, I. R. Iran
e-mail: ashrafi@kashanu.ac.ir, alir.ashrafi@gmail.com

Abstract.   Let G be a connected graph and ξ(G) = Sze(G) - We(G), where We(G) denotes the edge Wiener index and Sze(G) denotes the edge Szeged index of G. In an earlier paper, it is proved that if T is a tree then Sze(T) = We(T). In this paper, we continue our work to prove that for every connected graph G, Sze(G) ≥ We(G) with equality if and only if G is a tree. We also classify all graphs with ξ(G) ≤ 5. Finally, for each non-negative integer n ≠ 1 there exists a graph G such that ξ(G) = n.

2010 Mathematics Subject Classification.   05C12, 05A15, 05A20, 05C05.

Key words and phrases.   Edge Szeged index, edge Wiener index.

Full text (PDF) (free access)

DOI: 10.3336/gm.47.1.02

References:

  1. A. R. Ashrafi and M. Mirzargar, PI, Szeged and edge Szeged indices of nanostar dendrimers, Util. Math. 77 (2008), 249-255.
    MathSciNet    

  2. H.-J. Bandelt and H. M. Mulder, Distance-hereditary graphs, J. Combin. Theory Ser. B 41 (1986), 182-208.
    MathSciNet     CrossRef

  3. P. Dankelmann, I. Gutman, S. Mukwembi and H. C. Swart, The edge-Wiener index of a graph, Discrete Math. 309 (2009), 3452-3457.
    MathSciNet     CrossRef

  4. A. A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math. 66 (2001), 211-249.
    MathSciNet     CrossRef

  5. A. A. Dobrynin, I. Gutman, S. Klavzar and P. Zigert, Wiener index of hexagonal systems, Acta Appl. Math. 72 (2002), 247-294.
    MathSciNet     CrossRef

  6. A. Dobrynin and I. Gutman, On a graph invariant related to the sum of all distances in a graph, Publ. Inst. Math. (Beograd) (N.S.) 56(70) (1994), 18-22.
    MathSciNet    

  7. A. Dobrynin and I. Gutman, Solving a problem connected with distances in graphs, Graph Theory Notes of New York 28 (1995), 21-23.

  8. I. Gutman and A. R. Ashrafi, The edge version of the Szeged index, Croat. Chem. Acta 81 (2008), 263-266.

  9. I. Gutman, A formula for the Wiener number of trees and its extension to graphs containing cycles, Graph Theory Notes of New York 27 (1994), 9-15.

  10. P. Hliněný and J. Kratochvil, Computational complexity of the Krausz dimension of graphs, Graph-theoretic concepts in computer science (Berlin, 1997), 214-228, Lecture Notes in Comput. Sci., 1335, Springer, Berlin, 1997.
    MathSciNet    

  11. M. H. Khalifeh, H. Yousefi-Azari, A. R. Ashrafi and S. Wagner, Some new results on distance-based graph invariants, European J. Combin. 30 (2009), 1149-1163.
    MathSciNet     CrossRef

  12. H. Khodashenas, M. J. Nadjafi-Arani, A. R. Ashrafi and I. Gutman, A new proof of the Szeged-Wiener theorem, Kragujevac J. Math. 35 (2011), 165-172.
    MathSciNet    

  13. S. Klavžar, A. Rajapakse and I. Gutman, The Szeged and the Wiener index of graphs, Appl. Math. Lett. 9 (1996), 45-49.
    MathSciNet     CrossRef

  14. J. Krausz, Démonstration nouvelle d'une théorème de Whitney sur les réseaux, (Hungarian) Mat. Fiz. Lapok 50 (1943), 75-85.
    MathSciNet    

  15. A. Ilić, S. Klavžar and M. Milanović, On distance-balanced graphs, European J. Combin. 31 (2010), 733-737.
    MathSciNet     CrossRef

  16. I. Lukovits, An all-path version of the Wiener index, J. Chem. Inf. Comput. Sci. 38 (1998), 125-129.
    CrossRef

  17. R. Todeschini and V. Consonni, Handbook of molecular descriptors, Wiley, Weinheim, 2000.
    CrossRef

  18. N. Trinajstić, Chemical graph theory, CRC Press, Boca Raton, FL. 1992.

  19. D. B. West, Introduction to graph theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.

  20. H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932), 150-168.
    MathSciNet     CrossRef

  21. H. Wiener, Structural determination of the paraffin boiling points, J. Am. Chem. Soc. 69 (1947), 17-20.
    CrossRef

  22. S. Yousefi, H. Yousefi-Azari, A. R. Ashrafi and M. H. Khalifeh, Computing Wiener and Szeged indices of an achiral polyhex nanotorus, J. Sci. Univ. Tehran 33 (2007), 7-11.
    MathSciNet    
Glasnik Matematicki Home Page